560. 和为 K 的子数组

题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）

 

 

 

 

 

 

 

 

 

 

 

 

解析：

从左向右走，求前缀和，

pre[i] - pre[i - 1] == k 那说明存在一次

当知道pre[i]时，其实就是期望求有多少个pre[i - 1] = pre[i] - k

所以遍历同时记录当前前缀和个数，注意0初始化为个数1

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

        int n = nums.size(), cnt = 0;
        vector<int> prefix(n);
        map<int, int> vis;
        vis[0] = 1;
        prefix[0] = nums[0];
        if (nums[0] == k) {
            cnt++;
        }
        vis[prefix[0]]++;

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
            cnt += vis[prefix[i] - k];
            vis[prefix[i]]++;
        }
        return cnt;

        return cnt;
    }
};