[LeetCode] Subarray Sum Equals K | 前缀和+哈希表

https://leetcode.com/problems/subarray-sum-equals-k/#/description

要求是找数组中满足sum[i...j] = k的子数组数量，其中i <= j且sum[i...j]表示连续子数组nums[i...j]的和。

用prefix_sum[i]表示前缀和sum[0...i]，那么sum[i...j] = prefix_sum[j] - prefix_sum[i-1]，即目标是找prefix_sum[j] - prefix_sum[i-1] = k (i <= j)的数目。

计算前缀和的过程中，判断：

• 当前的前缀和prefix_sum[j]是否等于k，是的话计数器加1
• 目前已经计算出的所有前缀和是否有等于prefix_sum[j] - k的，有的话加上其出现次数（为了快速查找，可以用一个哈希表存下当前不同的前缀和的出现次数）

Time: O(n)
Extra space: O(n)

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        
        int n = nums.size();
        vector<int> prefix_sum(n, 0);
        unordered_map<int, int> m;  // key: prefix_sum, value: number of occurences
        int ret = 0;
        
        prefix_sum[0] = nums[0]; m[ nums[0] ] = 1;
        if (nums[0] == k) ret++; 
        for (int i = 1; i < n; ++i) {
            prefix_sum[i] = prefix_sum[i-1] + nums[i];
            if (prefix_sum[i] == k) ret++;
            if (m.find(prefix_sum[i]-k) != m.end()) {
                ret += m[ prefix_sum[i]-k ];
            }
            m[ prefix_sum[i] ]++;
        }
        
        return ret;
    }
};

相似问题:

• leetcode 523, Continuous Subarray Sum, https://leetcode.com/problems/continuous-subarray-sum/#/description
• leetcode 525, Contiguous Array, https://leetcode.com/problems/contiguous-array/#/description