小白爱刷题 523 ～ 连续 subarray 之和

基本信息

• 题号：523
• 题厂：微软
• 难度系数：中

已知一个数组和目标整数 k。问：数组中有没有一个连续的 subarray 的和刚好是 k 的整数倍……

例如：nums = [23,2,4,6,7], k = 6

2 + 4 = 6， 是 6 的一倍，于是返回 true

subarray 需要连续且至少包含 2 个元素。另外，0 也是有效整数倍……

解题思路

• 读懂题意后，发现本题和 #560 是一个套路，都是在数组里面折腾 subarray……
• #560 的解题关键是 「prefix 前缀和」，于是 523 的关键也是 prefix + hashmap
• 相对于 560， 523 还要多绕一圈：需要根据当前和与 k 之间的余数来判断到底改 subarray 存不存在……😵如果出现相同余数的前缀和，说明 subarray = k 的情况出现了🥲

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # hashmap 格式为：reaminder - index
        # 初始化时，当 index 为 -1 时余数为 0
        remainder = { 0: -1 }
        total = 0
        
        # for 循环时，如果当前和与 k 的余数不在 hashmap 里，就把当前「余数～index」更新到 hashmap 里
        # 为了确保 subarray 至少有两个元素，需要再检测 index 之差大于 1 才返回 true：[6], k = 6 应该返回 false，因为没有 2+ 元素……
        for i, n in enumerate(nums):
            total += n
            r = total % k
            
            if r not in remainder:
                remainder[total % k] = i
            elif i - remainder[r] > 1:
                return True
            
        return False

Constraints

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

Big O

• Time：O（n）
• Space：引入 hashmap，故 O（n）

测试

• 有满足的 subarray 和不满足的 subarray……
• 测试特殊情况各种 0……

总结

• 本题在 #560 的基础上又在余数问题上多绕了一圈，十分符合微软爱考数学 和 bit 的出题风格……
• 根据代码复杂度以及涉及的数据结构，本题被划归为中档，但解法真不容易想出来🙈。
• 本题可以和 #560 作为同系列「prefix 前缀和」配套复习。