Q525 连续数组（前缀和 + 哈希）

1
2
3
4

// ❌ 错误写法：{n+1,0} 是初始化列表，生成【两个元素：n+1、0】
vector<int> preSum{n+1,0};
// ✅ 正确写法：(容量,初始值)，开辟 n+1 个空间全部赋值 0
vector<int> preSum(n+1,0);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> preSum(n + 1, 0); // 重点：圆括号初始化
        // 构建前缀和
        for(int i = 0; i < n; ++i){
            preSum[i+1] = preSum[i] + (nums[i]==0 ? -1 : 1);
        }
        unordered_map<int, int> mp;
        mp[0] = 0; // 初始化边界
        int res = 0;
        for(int i = 1; i <= n; ++i){
            auto it = mp.find(preSum[i]);
            if(it == mp.end()){
                mp[preSum[i]] = i; // 首次出现才保存
            }else{
                res = max(res, i - it->second);
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> mp;
    mp[0]=-1;
    int sum=0,maxlen=0;
    for(int i=0;i<nums.size();i++){
        sum += nums[i]==1?1:-1;
        if(mp.count(sum)) maxlen=max(maxlen,i-mp[sum]);
        else mp[sum]=i;
    }
    return maxlen;
}