Subarray Sum Equals K

发表于 | 分类于

Subarray Sum Equals K

题目描述：

给定一个数组和一个目标值K，要求找到所有子数组的和为K的可能。

例子：

具体描述见LeetCode560

解题思路：

我们用哈希表记录下每次加上一个数组中的数的累加和以及出现的次数；然后每次加完之后我们可以通过key为累加值减去k判断当前是否能够构成一个字数粗和为k。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0;
        map<int, int> hash;
        hash[0]++;
        int cum = 0;
        for (int i = 0; i < nums.size(); i++){
            cum += nums[i];
            cnt += hash[cum - k];
            hash[cum]++;
        }
        return cnt;
    }
};