前缀和

525. 连续数组

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        /*
            由于以上碰1加一，碰0减一的操作，当0与1数量一致时(连续数组), 其连续数组的和为零。因此我们知道数组前面的 
            cur 值是什么，在到达该连续数组尾部时就不会变。因此我们只需要检查哈希表中是否存在其相同的 curcur 值即可
        */
        unordered_map<int, int> hash{{0, -1}};
        int cur = 0, ans = 0;
        for (int i = 0; i < nums.size(); i ++) {
            cur += nums[i] == 0 ? -1 : 1;
            if (hash.count(cur)) {
                ans = max(ans, i - hash[cur]);
            } else {
                hash[cur] = i;
            }
        }
        return ans;
    }
};

剑指 Offer II 010. 和为 k 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> hash;
        vector<int> s(n + 1, 0);
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1];
        hash[0] = 1; 
        int res = 0;
        // 类似双指针，哈希表存储的每个前缀和对应的个数，由于hash[0] = 1，
        // 它一定会转移到前嘴和-k为0的的位置，后面在确定其他前嘴和-当前前嘴和是否能被首前嘴和转移
        for (int i = 1; i <= n; i ++) {
            res += hash[s[i] - k];
            hash[s[i]] ++;
        }
        return res;
    }
};