LeetCode 523. 连续的子数组和
题目描述
题意分析
判断非负数组中是否存在长度至少为 2、元素和为
k的倍数的连续子数组。题目保证k > 0，和为 0 也符合要求；只需判断是否存在，不必找出区间。
解法：前缀和取模 + 最早位置
核心思路
[!blue]
设
P[i]是前i个元素的和，那么区间[l, r)的和为P[r] - P[l]，长度为r - l。要让这个差被k整除，等价于让两个前缀对k的余数相同。从左到右计算前缀和，用
first保存每种余数第一次出现时的前缀长度。当前余数若已出现，就检查两次前缀长度之差是否至少为 2。相同右端点下，最早的左前缀能得到最长区间：它都不够长，后面的同余前缀更不够长，因此每种余数只需保留最早位置。空前缀满足
P[0] = 0，所以先记录first[0] = 0，从数组开头开始的区间也能按同一规则判断。
解题步骤
- 初始化
first[0] = 0、前缀和sum = 0。- 加入当前元素，计算余数
key = sum % k。当前前缀长度在 Java 中是i，Go 中是i + 1。- 若
key已出现，取出最早长度start；当前长度减去start至少为 2 时返回true，否则继续并保留start。- 若
key首次出现，记录当前前缀长度。遍历结束仍未找到则返回false。
代码实现
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Long, Integer> first = new HashMap<>();
// 空前缀长度为零，覆盖从数组开头开始的区间。
first.put(0L, 0);
long sum = 0;
for (int i = 1; i <= nums.length; i++) {
sum += nums[i - 1];
long key = sum % k;
Integer start = first.get(key);
if (start != null) {
// 同余还必须满足长度至少为二，不够长时也保留最早位置。
if (i - start >= 2) {
return true;
}
} else {
first.put(key, i);
}
}
return false;
}
}
func checkSubarraySum(nums []int, k int) bool {
// 空前缀长度为零，覆盖从数组开头开始的区间。
first := map[int64]int{0: 0}
var sum int64
for i, num := range nums {
sum += int64(num)
key := sum % int64(k)
if start, exists := first[key]; exists {
// 同余还必须满足长度至少为二，不够长时也保留最早位置。
if i+1-start >= 2 {
return true
}
} else {
first[key] = i + 1
}
}
return false
}
复杂度分析
- 时间复杂度：期望 $O(n)$，其中
n是数组长度；每个元素做常数次哈希操作。- 空间复杂度：$O(\min(n+1,k))$，共有
n + 1个前缀，余数最多有k种。
关键点总结
[!green]
- 前缀和把区间和转成两个前缀之差，同余关系把整除判断转成哈希查找。
- 保留最早的同余前缀，才能在每个右端点检查最长候选。
- 表里存前缀长度，长度差正好就是子数组长度。
易错点总结
[!yellow]
- 同余只是和满足要求，还必须检查长度至少为 2；数组只有一个元素时自然返回
false。- 命中后即使长度不足，也不能覆盖最早位置，否则可能漏掉后续答案。
- 忘记空前缀会漏掉从数组开头开始的区间。
- 不能排除和为 0 的区间，它同样是正整数
k的倍数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 同样利用两前缀关系，原题要求差等于k，本题要求差为k的倍数并限制长度至少2。 |
| 974. 和可被 K 整除的子数组 | 中等 | 同样按前缀余数分组，原题计所有合格区间，本题只需判断是否存在且满足长度约束。 |
| 1590. 使数组和能被 P 整除 | 中等 | 按前缀和余数分类；本题寻找相同余数且距离至少为二的前缀，该题查找应删区间的余数差并最小化长度。 |
| 补充题 128. 和为 k 的倍数的最短子数组 | 中等 | 都用相同前缀余数判定区间和是 k 的倍数；本题保留最早位置判存在，补充题保留最近位置求最短。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！