** 不知道叫什么名字

男生加一,女生减一,从而把问题转化为和为0的一串最长的数组。

整体思路是利用前缀和的思想,通过哈希表记录前缀和第一次出现的位置,然后遍历数组,如果遇到相同的前缀和,说明中间的子数组0和1的数量相等,更新最长子数组的长度。

上代码:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> prefixSum;  // 哈希表,记录前缀和第一次出现的位置
    int sum = 0;
    int maxLen = 0;

    prefixSum[0] = 0;  // 初始前缀和为0的位置为0

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            sum -= 1;
        } else {
            sum += 1;
        }
        
        if (prefixSum.count(sum)) {
            maxLen = max(maxLen, i - prefixSum[sum]);
        } else {
            prefixSum[sum] = i;
        }
    }

    cout << maxLen;
    return 0;
}