> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/560-he-weikde-zi-shu-zu.md).

# \[560]\[中等]\[前缀和]\[哈希] 和为K的子数组

## 题目描述

[560. 和为K的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k/)

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

```
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
```

说明 :

* 数组的长度为 \[1, 20,000]。
* 数组中元素的范围是 \[-1000, 1000] ，且整数 k 的范围是 \[-1e7, 1e7]。

## 解题思路

暴力法是枚举出所有**连续自数组**, 判断是否符合条件, 遍历数组, 对于每个`i`, 都要枚举所有`[j, i]`这样的子数组. 优化就是通过**前缀和**的方法.

定义前缀和数组`pre`, `pre[i]`代表`nums[0, 1, ..., i - 1]`的和, 这样`pre[i]`可以由`pre[i - 1]`递推而来. 即`pre[i] = pre[i - 1] + nums[i - 1]`. `pre`前缀和数组的长度为`n + 1`, `n`是原数组`nums`的长度, `pre[0]`由于没有对应的前缀, 我们定义值为0.

![](/files/-MGZERVV6vTAQuBgSQ9C)

那么每个连续子数组的和`k`就可以由前缀和数组得到: `k = pre[i + 1] - pre[j]`, 代表`[j, i]`子数组之和. 因此在遍历到`i`位置时, 计算出前缀和`pre[i + 1]`的同时, 我们也可以计算出当前位置如果要满足子数组和`k`对应的`pre[j]`, 而`pre[j] = pre[i + 1] - j`, 因此, 我们下一步的目标就是寻找值为`pre[j] = pre[i + 1] - j`的前缀和位置由多少.

因此, 为了搜索的快捷, 不会使用数组去存储前缀和, 而是使用**哈希表**. key值为前缀和值, value是当前前缀和对应的出现次数. 因此只需要遍历一次数组, 就能够得到满足条件的连续子数组的个数了.

```python
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        mapping = {0: 1}
        ans, suffix = 0, 0
        for i, num in enumerate(nums):
            suffix += num
            resi = suffix - k
            if resi in mapping:
                ans += mapping[resi]
            mapping[suffix] = mapping[suffix] + 1 if suffix in mapping else 1
        return ans
```