基本信息

  • 题号：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 前缀和」配套复习。