LeetCode 523：连续的子数组和 | 前缀和同余定理

LeetCode 523连续的子数组和 | 前缀和同余定理引言连续的子数组和Continuous Subarray Sum是 LeetCode 第 523 题难度为 Medium。题目要求判断数组中是否存在长度至少为 2 的连续子数组其元素和是 K 的倍数。这道题是前缀和与数论中同余定理结合的经典案例展示了如何将数学知识应用于算法问题。这道题的核心思想是如果两个前缀和对 K 取模后的余数相同那么这两个前缀和之差对应的子数组和一定是 K 的倍数。利用这个性质我们可以使用哈希表记录每个前缀和余数首次出现的位置从而高效地判断是否存在满足条件的子数组。问题分析题目描述给定一个整数数组 nums 和一个整数 K判断数组中是否存在长度至少为 2 的连续子数组其元素和是 K 的倍数。如果存在返回 True否则返回 False。例如输入 nums [23, 2, 6, 4, 7]K 6输出为 True因为子数组 [23, 2, 6, 4] 的和是 3535 是 6 的倍数35 5 * 6 5但 35 不是 6 的倍数这里有点问题子数组 [6, 4] 的和是 1010 不是 6 的倍数。实际上子数组 [2, 6] 的和是 88 不是 6 的倍数。正确的例子应该是如果 nums [23, 2, 4, 6]K 6输出为 True因为子数组 [2, 4, 6] 的和是 12是 6 的倍数。同余定理同余定理是数论中的重要概念。对于整数 a、b 和正整数 K如果 K 整除 (a - b)即 (a - b) % K 0我们称 a 和 b 同余记作 a ≡ b (mod K)。在子数组和问题中对于两个前缀和 prefixSum[i] 和 prefixSum[j]j i如果 (prefixSum[j] - prefixSum[i]) % K 0即 prefixSum[j] % K prefixSum[i] % K那么子数组 nums[i:j-1] 的和是 K 的倍数。哈希表方法def checkSubarraySum(nums, k): prefix_sum 0 index_map {0: -1} for i, num in enumerate(nums): prefix_sum num mod prefix_sum % k if k ! 0 else prefix_sum if mod in index_map: if i - index_map[mod] 2: return True else: index_map[mod] i return False这个方法使用哈希表记录每个前缀和对 K 取模后首次出现的位置。如果当前模已经在哈希表中说明存在两个前缀和同余可以构成 K 的倍数的子数组。算法详解前缀和同余对于子数组 nums[l:r1]其和 prefixSum[r1] - prefixSum[l]。这个和是 K 的倍数当且仅当 (prefixSum[r1] - prefixSum[l]) % K 0即 prefixSum[r1] % K prefixSum[l] % K。因此我们需要找到两个相同的模且它们之间的距离至少为 2对应子数组长度至少为 2。哈希表的设计哈希表 index_map 存储每个模首次出现的索引。初始化为 {0: -1}表示前缀和为 0空数组的前缀和出现在索引 -1。这个初始化工件理了从头开始的子数组。当遍历到索引 i 时计算当前模 mod prefixSum % KK ! 0 时。如果 mod 已经在哈希表中说明之前存在相同模的位置 j索引为 index_map[mod]。此时子数组 nums[j1:i] 的和是 K 的倍数。如果 i - index_map[mod] 2说明子数组长度至少为 2满足条件。如果 mod 不在哈希表中将其加入哈希表。注意如果 mod 已存在我们不更新哈希表因为题目要求的是最长子数组或任意长度 2 的子数组不更新哈希表可以保证后续检查的是最早出现的位置从而得到最长的子数组。K 为零的情况当 K 0 时我们需要找的是和恰好为 0 的子数组。这与 K ! 0 的情况不同需要特殊处理。在代码中当 K 0 时我们直接用 prefix_sum 而不用取模后的值。这意味着我们需要找两个相等的前缀和且距离至少为 2。复杂度分析时间复杂度时间复杂度为 O(n)因为我们只遍历数组一次每次迭代只进行常数次的哈希表操作。空间复杂度空间复杂度为 O(n)在最坏情况下哈希表需要存储 K 个不同的模如果 K 不为 0模的范围是 0 到 K-1。实际上最多存储 n1 个条目。代码实现Python 实现def checkSubarraySum(nums, k): prefix_sum 0 index_map {0: -1} for i, num in enumerate(nums): prefix_sum num if k ! 0: mod prefix_sum % k else: mod prefix_sum if mod in index_map: if i - index_map[mod] 2: return True else: index_map[mod] i return FalseJava 实现public boolean checkSubarraySum(int[] nums, int k) { MapInteger, Integer indexMap new HashMap(); indexMap.put(0, -1); int prefixSum 0; for (int i 0; i nums.length; i) { prefixSum nums[i]; int mod k ! 0 ? prefixSum % k : prefixSum; if (indexMap.containsKey(mod)) { if (i - indexMap.get(mod) 2) { return true; } } else { indexMap.put(mod, i); } } return false; }边界情况处理空数组或单元素数组当数组为空或只有一个元素时不可能存在长度至少为 2 的子数组应该返回 False。代码在这种情况下会直接返回 False。全零子数组当 K 6 且子数组 [0, 0] 的和为 0是 6 的倍数。代码中当 K ! 0 时mod 0 % 6 0与初始的 {0: -1} 相同i - (-1) 1 2不会返回 True。当遍历到第二个 0 时mod 仍然是 0此时 i - (-1) 2 2返回 True。负数处理前缀和可以是负数负数取模在 Python 和 Java 中的行为略有不同。Python 的 % 运算符总是返回与除数同号的结果而 Java 的 % 运算符返回与被除数同号的结果。在实际实现中我们需要确保取模逻辑的一致性。在 Python 中负数 % 正数的取模结果是正数这符合我们的需求。在 Java 中负数 % 正数的结果是负数可能需要调整。在 LeetCode 中Python 实现通常不需要特别处理。K 为负数如果 K 是负数可以将其转换为正数处理因为取模运算中 -K 和 K 是等价的。在代码中我们可以先取 k abs(k)。测试用例def test_check_subarray_sum(): assert checkSubarraySum([23, 2, 4, 6], 6) True assert checkSubarraySum([23, 2, 6, 4, 7], 6) False assert checkSubarraySum([23, 2, 6, 4, 7], 13) False assert checkSubarraySum([0, 0], 0) True assert checkSubarraySum([0, 0], 1) True assert checkSubarraySum([1, 2, 3], 5) True assert checkSubarraySum([1, 2, 3], 7) False assert checkSubarraySum([], 1) False print(所有测试用例通过)扩展问题返回子数组的起始和结束位置如果题目要求返回具体的子数组位置我们可以修改代码在找到满足条件的子数组时返回 (index_map[mod] 1, i)。长度至少为 3如果题目要求长度至少为 3只需要将条件 i - index_map[mod] 2 改为 3 即可。统计满足条件的子数组数量如果题目改为统计满足条件的子数组数量我们需要将哈希表中的值从首次出现的索引改为出现的次数然后在遍历时累加计数。总结连续的子数组和问题展示了前缀和与同余定理结合的巧妙应用。通过将和是 K 的倍数转化为两个前缀和同余我们可以在 O(n) 时间内解决这个看似需要 O(n²) 的问题。这个问题的关键洞察是子数组和是 K 的倍数 两个前缀和对 K 同余。利用哈希表记录每个模首次出现的位置我们可以在遍历过程中快速判断是否存在满足条件的子数组。希望通过本文的讲解读者能够掌握同余定理在算法问题中的应用并将其推广到更多类似问题的解决中。