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

题目描述

523. 连续的子数组和

给定一个包含 非负数 的数组和一个目标 整数 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的子数组中, 每个位置$i$, 我们寻找的是以其作为结尾的所有连续子数组中, 和的值为$k$的. 所以本题中我们可以转变一下思路, 还是使用前缀和, 但前缀和不再存储原始的和值, 而是存储前缀和对$k$的余数, 这样对于某个位置, 我们求得其前缀和的余数为$r$, 只需要找之前的前缀中, 是否有余数也为$r$的位置, 且这两个位置之差至少为2, 如果满足, 就找到了满足条件的子数组.

需要注意几点:

• 哈希表的key值为前缀和的余数, 值为这个余数第一次出现的位置; 后面再次遇到, 判断距离即可

• 对于余数为0的情况, 即可以整除, 就可能产生了答案, 无需再向下走. 因此, 不能遇到这种情况, 再向哈希表中添加余数为0的位置, 这样可能错过正确的答案. 因此在初始化哈希表时, 向其中添加0: -1的键值对. 这样如果数组的前两个位置之和是$k$的正整数倍, 就产生了结果

• 由于我们只关心余数, 因此不需要记录真正的前缀和, 而是一直记录前缀和余数, 对于新的位置, 前一步的余数加上这个值, 再求对$k$的余数, 这样得到的余数就是正确的

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的更新规则也要改变.