# 560.和为K的子数组

[https://leetcode-cn.com/problems/subarray-sum-equals-k/](https://leetcode-cn.com/problems/subarray-sum-equals-k/)

先计算前缀和，然后双指针i，j遍历，i从`1~n`，j从`0~i-1`，若有`preSum[i] - preSum[j] == k`，说明`nums[j+1...i]`的和为k

```python
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        preSum = [0]*(n+1)
        for i in range(n):
            preSum[i+1] = preSum[i] + nums[i]
        count = 0	#计数器
        for i in range(1, n+1):
            for j in range(i):
                if preSum[i] - preSum[j] == k:
                    count +=1
        return count
```

上面方法超时

### 改进

`preSum[i] - preSum[j] = k` 变式为 `preSum[j] = preSum[i] - k`

因为i>j，所以preSum\[i]一定先于preSum\[j]计算出来，每次将求出的preSum\[i]记录在map，若得到的preSum\[j]存在于map，说明符合题意

```python
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        map = {}  # key为前缀和，value为出现次数
        map[0] = 1
        preSum_i = 0
        count = 0
        for i in range(n):
            preSum_i += nums[i]
            preSum_j = preSum_i - k
            if preSum_j in map:     #看preSum[j]是否已被计算出来
                count += map[preSum_j]
            map[preSum_i] = map.get(preSum_i, 0) + 1    #更新map

        return count
```
