LeetCode 补充题 128. 和为 k 的倍数的最短子数组
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 523. 连续的子数组和
:::
给你一个 32 位整数数组
nums和一个正整数k，请返回元素和能够被k整除的最短非空连续子数组的长度。数组中允许有负数，长度为
1的子数组也合法。如果不存在符合条件的子数组，返回-1。
示例 1：
输入：
nums = [2,3,1,2], k = 3
输出：1
解释： 单元素子数组[3]的和已能被3整除。
示例 2：
输入：
nums = [1,1,1], k = 3
输出：3
解释： 只有整个数组的和能被 3 整除。
示例 3：
输入：
nums = [1], k = 2
输出：-1
解释： 没有满足要求的非空连续子数组。
提示：
- 数组元素为
32位整数，允许负数。 -
k为正整数。 - 子数组必须非空，长度
1也合法。
题意分析
子数组和等于右侧前缀和减去左侧前缀和，能被
k整除等价于两个前缀和模k相等。数组允许负数，不能用窗口和单调增减的假设，前缀同余关系则始终成立。
解法：前缀余数配对最近位置
核心思路
[!blue]
扫描到下标
i时，只需知道当前前缀余数上一次出现的位置last，合法子数组长度就是i - last。固定右端点时，左端越近长度越短，所以每个余数只保留最近位置，更早位置不会产生更优答案。初始化余数 0 对应位置 -1，覆盖从下标 0 开始的合法子数组。每步先用旧位置计算长度，再覆盖为当前位置，避免把空区间误算成长度 0；Java 的
put返回被覆盖的旧值，作用相同。将负数余数归一化到
[0,k-1]，使数学上同余的前缀拥有相同键。累计时仅保存余数，不必累加完整前缀和；若始终没有配对则返回 -1。
解题步骤
- 预置余数 0 的位置为 -1，表示空前缀。
- 逐个累加并归一化余数，取得该余数上次出现的位置。
- 有旧位置就更新长度差，再让当前位置成为最新位置；无候选返回 -1。
代码实现
class Solution {
public int shortestMultiple(int[] a, int k) {
Map<Long, Integer> latest = new HashMap<>();
latest.put(0L, -1);
long remainder = 0;
int best = a.length + 1;
for (int i = 0; i < a.length; i++) {
remainder = Math.floorMod(remainder + a[i], (long) k);
Integer last = latest.put(remainder, i);
if (last != null) {
best = Math.min(best, i - last);
}
}
return best <= a.length ? best : -1;
}
}
func shortestMultiple(a []int, k int) int {
latest := map[int64]int{0: -1}
remainder := int64(0)
best := len(a) + 1
mod := int64(k)
for i, v := range a {
remainder = ((remainder+int64(v))%mod + mod) % mod
if last, ok := latest[remainder]; ok {
best = min(best, i-last)
}
latest[remainder] = i
}
if best > len(a) {
return -1
}
return best
}
复杂度分析
- 时间复杂度：期望 $O(n)$。
- 空间复杂度：额外空间 $O(\min (n,k))$。
关键点总结
[!green]
同余关系确定合法性，保存最近或最早位置则由最短或最长目标决定，不能机械复用同一张位置表。
易错点总结
[!yellow]
初始余数0对应位置-1；负数余数需归一化。若另要求长度至少2，不能直接套用当前最近位置策略。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 523. 连续的子数组和 | 中等 | 原题要求长度至少 2 并判断存在，本题允许长度 1 且求最短，不能直接复用最早位置策略。 |
| 974. 和可被 K 整除的子数组 | 中等 | 同余前缀的判据相同；计数题存频次，最短长度题存最近下标。 |