523 连续的子数组和（枚举、前缀和、哈希表）

秒速五厘米 2022-08-30 05:15 203阅读 0赞

**1. 问题描述：**

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：  
子数组大小至少为 2 ，且子数组元素总和为 k 的倍数。如果存在，返回 true ；否则，返回 false 。如果存在一个整数 n ，令整数 x 符合 x = n \* k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

**示例 1：**

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

**示例 2：**

输入：nums = \[23,2,6,4,7\], k = 6  
输出：true  
解释：\[23, 2, 6, 4, 7\] 是大小为 5 的子数组，并且和为 42 。  
42 是 6 的倍数，因为 42 = 7 \* 6 且 7 是一个整数。

**示例 3：**

输入：nums = \[23,2,6,4,7\], k = 13  
输出：false

**提示：**

1 <= nums.length <= 10 ^ 5  
0 <= nums\[i\] <= 10 ^ 9  
0 <= sum(nums\[i\]) <= 2 ^ 31 - 1  
1 <= k <= 2 ^ 31 - 1  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/continuous-subarray-sum

**2. 思路分析：**

对于这种题目我们首先考虑如何枚举才能将所有答案都枚举到，一般枚举的是以当前的i为终点..，对于这道题目来说我们可以枚举以当前的i为终点的所有区间和是否是k的倍数，计算某个区间的区间和我们可以使用前缀和，所以问题就转化为了判断以当前位置i结尾的所有区间的区间和是否是k的倍数，也即判断si - si-2， si - si-3...si - s0是否是k的倍数，进一步等价为si - 2,si - 3...s0除以k的余数是否等于si除以k的余数，如何快速判断之前是否存在一个数字呢？这里可以使用哈希表将之前的si-2个前缀和模k的余数存起来（边遍历边存储前缀和即可，**哈希表优化技巧**，与之前的前缀和 + 哈希表优化的题目也是类似的，需要判断判断某个数是否之前出现过），然后判断当前的si % k在哈希表中是否存在如果存在说明是满足条件的。（主要是如何枚举的思维然后如何分析得到当前问题问题的等价问题）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 因为这里的k都是大于0的所以不用特判k=0的情况
        def checkSubarraySum(self, nums: List[int], k: int) -> bool:
            n = len(nums)
            s = [0] * (n + 1)
            # 前缀和
            for i in range(1, n + 1):
                s[i] += s[i - 1] + nums[i - 1]
            dic = dict()
            for i in range(2, n + 1):
                # 在循环中存储之前的前i-2项前缀和(要求前缀和长度大于等于2所以存储前i-2项)
                dic[s[i - 2] % k] = 1
                if s[i] % k in dic: return True
            return False

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/56e369c8246a493f82d61ab73caffc59.png