525. 连续数组(前缀和c++)

525. 连续数组(前缀和/c++)

class Solution {
public:
    int findMaxLength(vector& nums) {
        if(nums.size() == 1){
            return 0;
        }
        int count = 0;//前缀和
        unordered_mapmp;//存放前缀和，和前缀和的索引
        mp[count] = -1;//
        int max_len = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0){
                count--;
            }else{
                count++;//计算前缀和，num[i]为0时，加-1
            }
            if(mp.count(count)){//如果存在哈希表之前存在这个前缀和count
                int preindex = mp[count];//preindex代表之前存在的前缀和的索引
                max_len = max(max_len, i - preindex);//i - preindex计算两个相等的前缀和的索引之差,索引之差即为所求的最长连续数组
            }else{
                mp[count] = i;//如果哈希表不存在这个前缀和，则存入前缀和和索引
            }
        }
        return max_len;
    }
};