560_SubarrayEqualsK - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //      1   1   1
        //sum   1   2   3
        // dict = {{0,1}}
        // i = 0, dict = {{0,1}, {1,1}};
        // i = 1, dict = {{0,1},{1,1},{2,1}};
        // i = 2, dict = {{0,1},{1,1},{2,1}, {3,1}};
        // hash table 代表子陣列總和與其次數
        int count = 0, n = nums.size(), sum=0;
        unordered_map<int,int> sub;
        sub[0] = 1;
        for(int i=0;i<n;++i){
            sum+=nums[i];
            if(sub.find(sum-k)!=sub.end()) count+=sub[sum-k];
            sub[sum]++;
        }
        return count;
        
    }
};