> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/sum2index/subarray-sum-equals-k.md).

# Subarray Sum Equals K

> Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
>
> Example 1:
>
> Input:nums = \[1,1,1], k = 2
>
> Output: 2
>
> Note:
>
> The length of the array is in range \[1, 20,000].
>
> The range of numbers in the array is \[-1000, 1000] and the range of the integer k is \[-1e7, 1e7].

## Thoughts

统计所有满足和为K的子数组数目。subarray sum问题无非用presum或DP。这道题和普通subarray sum区别前者统计频率，后者只是问是否存在，思路一致的，对每个presum记录下频率。

## Code

```cpp
/*
 * @lc app=leetcode id=560 lang=cpp
 *
 * [560] Subarray Sum Equals K
 */

// @lc code=start
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> presum;
        presum[0] = 1;
        int s = 0, res = 0;
        for (const auto num : nums) {
            s += num;
            if (presum.count(s - k)) res += presum[s - k];
            if (!presum.count(s)) presum[s] = 0;
            ++presum[s]; 
        }
        return res;
    }
};
// @lc code=end


```

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> sums = new HashMap<>();
        sums.put(0, 1);
        int res = 0;
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sums.containsKey(sum - k)) {
                res += sums.get(sum - k); 
            }
            sums.put(sum, sums.getOrDefault(sum, 0) + 1);
        }

        return res;
    }
}
```

## Analysis

时间复杂度O(N), 空间O(N).