当前位置：首页 > news >正文

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

news 2026/5/24 4:21:09

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] 的和是 35，35 是 6 的倍数（35 = 5 * 6 + 5，但 35 不是 6 的倍数，这里有点问题），子数组 [6, 4] 的和是 10，10 不是 6 的倍数。实际上，子数组 [2, 6] 的和是 8，8 不是 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:r+1]，其和 = prefixSum[r+1] - prefixSum[l]。这个和是 K 的倍数当且仅当 (prefixSum[r+1] - prefixSum[l]) % K == 0，即 prefixSum[r+1] % K == prefixSum[l] % K。

因此，我们需要找到两个相同的模，且它们之间的距离至少为 2（对应子数组长度至少为 2）。

哈希表的设计

哈希表 index_map 存储每个模首次出现的索引。初始化为 {0: -1}，表示前缀和为 0（空数组的前缀和）出现在索引 -1。这个初始化工件理了从头开始的子数组。

当遍历到索引 i 时，计算当前模 mod = prefixSum % K（K != 0 时）。如果 mod 已经在哈希表中，说明之前存在相同模的位置 j，索引为 index_map[mod]。此时，子数组 nums[j+1: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）。实际上最多存储 n+1 个条目。

代码实现

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 False

Java 实现

public boolean checkSubarraySum(int[] nums, int k) { Map<Integer, 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("所有测试用例通过！")