1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：

一个 好的子数组 是：

• 长度 至少为 2 ，且

• 子数组元素总和为 k 的倍数。

注意：

• 子数组 是数组中 连续 的部分。

• 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。

1.2.题目地址

https://leetcode.cn/problems/continuous-subarray-sum/description/

2.解题方法

2.1.解题思路

前缀和+哈希表

2.2.解题步骤

第一步，统计nums的前缀和，得到数组preSums

第二步，求preSums各项对k的余数，如果存在距离大于等于2的相同余数项，则代表存在「好的子数组」，这里使用哈希表记录每个余数项第一次出现的位置进行判断

3.解题代码

python3代码

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # 思路：前缀和+哈希表
        # 第一步，统计nums的前缀和，得到数组preSums
        preSums = [0]
        for num in nums:
            preSums.append(preSums[-1] + num)
        # 第二步，求preSums各项对k的余数，如果存在距离大于等于2的相同余数项，则代表存在「好的子数组」，这里使用哈希表记录每个余数项第一次出现的位置进行判断
        modVals = [sum1 % k for sum1 in preSums]
        map1 = {}
        for i, mod in enumerate(modVals):
            if mod in map1:
                if i - map1[mod] >= 2:
                    return True
            else:
                map1[mod] = i
        return False

4.执行结果