> For the complete documentation index, see [llms.txt](https://kerasnoone.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://kerasnoone.gitbook.io/garnet/suan-fa/shu-zu/523-lian-xu-de-zi-shu-zu-he.md).

# \[523]\[中等]\[前缀和]\[哈希] 连续的子数组和

## 题目描述

[523. 连续的子数组和](https://leetcode-cn.com/problems/continuous-subarray-sum/)

给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n\*k，其中 n 也是一个整数。

示例 1：

```
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
```

示例 2：

```
输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
```

说明：

* 数组的长度不会超过 10,000 。
* 你可以认为所有数字总和在 32 位有符号整数范围内。

## 解题思路

对于每个位置$$i$$, 我们要寻找以其作为结尾的所有连续子数组中, 和是$$k$$的正数倍的. 在[\[560\]\[中等\]\[前缀和\]\[哈希\] 和为K的子数组](/garnet/suan-fa/shu-zu/560-he-weikde-zi-shu-zu.md)中, 每个位置$$i$$, 我们寻找的是以其作为结尾的所有连续子数组中, 和的值为$$k$$的. 所以本题中我们可以转变一下思路, 还是使用前缀和, 但前缀和不再存储原始的和值, 而是存储**前缀和对**$$k$$**的余数**, 这样对于某个位置, 我们求得其前缀和的余数为$$r$$, 只需要找之前的前缀中, 是否有余数也为$$r$$的位置, 且这两个位置之差至少为2, 如果满足, 就找到了满足条件的子数组.

需要注意几点:

* 哈希表的key值为前缀和的余数, 值为这个余数第一次出现的位置; 后面再次遇到, 判断距离即可
* 对于余数为0的情况, 即可以整除, 就可能产生了答案, 无需再向下走. 因此, 不能遇到这种情况, 再向哈希表中添加余数为0的位置, 这样可能错过正确的答案. 因此在初始化哈希表时, 向其中添加`0: -1`的键值对. 这样如果数组的前两个位置之和是$$k$$的正整数倍, 就产生了结果
* 由于我们只关心余数, 因此不需要记录真正的前缀和, 而是一直记录前缀和余数, 对于新的位置, 前一步的余数加上这个值, 再求对$$k$$的余数, 这样得到的余数就是正确的

```python
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        mapping = {0: -1}
        total = 0

        for i, num in enumerate(nums):
            total += num
            if k != 0:
                total = total % k
            if total in mapping:
                if i - mapping[total] >= 2:
                    return True
            else:
                mapping[total] = i
        return False
```

其实上面的代码中有个`bug`, 对于`nums=[3,0,0,0,0], k=6`这种测试用例, 也是会返回`True`的. 但在`Leetcode`可以通过, 说明其用例也没有考虑这种情况. 正确的做法应当是哈希表中除了位置, 还要记录总值大小, 这样在余数相等时, 还要再比较两个位置前缀和的总大小是否相等. 这样, `total`的更新规则也要改变.