** 不知道叫什么名字
男生加一,女生减一,从而把问题转化为和为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;
}