连续的子数组和

难度: Medium

给你一个整数数组 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⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Submission

运行时间: 55 ms

内存: 30.7 MB

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        model=set()
        presum=0
        for num in nums:
            last=presum
            presum+=num
            presum%=k
            if presum in model:
                return True
            model.add(last)
        return False

Explain

这个题解使用了前缀和和哈希表来解决问题。首先计算数组的前缀和，然后在遍历过程中，判断当前前缀和对 k 取模的结果是否已经在哈希表中出现过。如果出现过，说明存在一个子数组，它的元素和为 k 的倍数。同时，为了确保子数组的大小至少为 2，哈希表中存储的是前一个前缀和对 k 取模的结果。

时间复杂度: O(n)

空间复杂度: O(min(n, k))

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        model = set()  # 哈希表，用于存储前缀和对 k 取模的结果
        presum = 0  # 前缀和变量
        
        for num in nums:
            last = presum  # 记录前一个前缀和对 k 取模的结果
            presum += num  # 更新前缀和
            presum %= k  # 前缀和对 k 取模
            
            if presum in model:  # 如果当前前缀和对 k 取模的结果已经在哈希表中出现过
                return True  # 说明存在一个子数组，它的元素和为 k 的倍数
            
            model.add(last)  # 将前一个前缀和对 k 取模的结果加入哈希表
        
        return False  # 如果遍历完整个数组都没有找到满足条件的子数组，返回 False

Explore

前缀和技术能够快速计算任意子数组的和。通过使用前缀和，我们可以计算从数组的任意位置 i 到 j 的子数组和为 `prefixSum[j] - prefixSum[i-1]`。结合哈希表来存储前缀和的模结果，我们可以快速检查是否存在两个前缀和的模 k 结果相同，这意味着从 i 到 j 的子数组和是 k 的倍数。哈希表提供了常数时间的查找效率，这极大地提高了整体算法的效率，使得我们不需要对每个子数组都重复计算和检查。

存储前一个前缀和对 k 取模的结果而非当前前缀和的目的是为了确保我们找到的子数组长度至少为 2。这种方法防止了仅通过当前元素或紧接当前元素的单个元素组成的子数组满足条件的情况，因为这样的子数组长度会小于 2。通过先将前一个模结果存入哈希表，再更新当前前缀和，我们能确保任何时候检测到模结果已存在时，至少包含两个元素的子数组被考虑。

当我们发现前缀和对 k 取模的结果已经存在于哈希表中时，这意味着至少有两个不同的前缀和有相同的模 k 结果。设两个前缀和分别为 `prefixSum[i]` 和 `prefixSum[j]`（其中 i < j），并且它们对 k 取模的结果相同，即 `prefixSum[i] % k == prefixSum[j] % k`。根据同余定理，这意味着 `(prefixSum[j] - prefixSum[i]) % k == 0`，即从 i+1 到 j 的子数组和为 k 的倍数。因此，我们可以断定存在这样一个子数组，其和为 k 的倍数。

直接存储每个前缀和的模 k 的结果而不是前缀和本身的优势包括：1) 节省空间，因为模 k 的结果范围限制在 0 到 k-1，而前缀和的值可能非常大；2) 提高效率，因为比较模 k 的结果比比较大整数更快；3) 直接相关于问题要求，我们关心的是子数组和是否为 k 的倍数，而这可以通过检查模 k 结果是否相等直接得到。这种方法提供了一种更直接且效率更高的方式来检查子数组和是否满足特定条件。