LeetCode 1590中等前缀和/哈希
使数组和能被 P 整除 图解题解
这道题到底在问什么
给正整数数组 nums 和整数 p，删除一个最短的（可为空）连续子数组，使剩余元素和能被 p 整除（总和本就能被 p 整除时删空段、返回 0）；不能删整个数组，无解返回 −1。
- 输入
- nums=[3,1,4,2], p=6
- 输出
- 1（删 [4] 剩 6）
- 输入
- nums=[6,3,5,2], p=9
- 输出
- 2（删 [5,2] 剩 9）
最优解：一步一步想明白
- 3记住「删的段和 ≡ need；找余数 = target 的最近前缀」，下面每帧都在套它。
- 4先算整段和 29，29 mod 6 = 5 就是 need。目标:删一段使其和 ≡ 5 (mod 6)，剩下的就能被 6 整除。先把空前缀记下:余数 0 在下标 −1。
- 5读第 0 位 4，累进前缀和再取模:prefix 从 0 变成 4。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 6target = 5 不在表里，没有以这里结尾的可删段。把当前前缀余数记下 last[4] = 0(只留最近的，求最短才对)，留给后面用。
- 7读第 1 位 3，累进前缀和再取模:prefix 从 4 变成 1。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 8target = 2 不在表里，没有以这里结尾的可删段。把当前前缀余数记下 last[1] = 1(只留最近的，求最短才对)，留给后面用。
- 9读第 2 位 1，累进前缀和再取模:prefix 从 1 变成 2。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 10target = 3 不在表里，没有以这里结尾的可删段。把当前前缀余数记下 last[2] = 2(只留最近的，求最短才对)，留给后面用。
- 11读第 3 位 4，累进前缀和再取模:prefix 从 2 变成 0。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 12target = 1 在表里(最近下标 1)！删掉下标 2…3 这段(窗口)，剩余和就 ≡ 0 (mod 6)，这段长 2。比之前更短，最短刷新成 2。 再把 last[0] 更新成 3。
- 13读第 4 位 2，累进前缀和再取模:prefix 从 0 变成 2。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 14target = 3 不在表里，没有以这里结尾的可删段。把当前前缀余数记下 last[2] = 4(只留最近的，求最短才对)，留给后面用。
- 15读第 5 位 5，累进前缀和再取模:prefix 从 2 变成 1。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 16target = 2 在表里(最近下标 4)！删掉下标 5…5 这段(窗口)，剩余和就 ≡ 0 (mod 6)，这段长 1。比之前更短，最短刷新成 1。 再把 last[1] 更新成 5。
- 17读第 6 位 7，累进前缀和再取模:prefix 从 1 变成 2。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 18target = 3 不在表里，没有以这里结尾的可删段。把当前前缀余数记下 last[2] = 6(只留最近的，求最短才对)，留给后面用。
- 19读第 7 位 3，累进前缀和再取模:prefix 从 2 变成 5。下一步算 target、去哈希表里找余数 = target 的最近位置。
- 20target = 0 在表里(最近下标 3)！删掉下标 4…7 这段(窗口)，剩余和就 ≡ 0 (mod 6)，这段长 4。没比当前最短 1 更短，保持。 再把 last[5] 更新成 7。
- 21扫完全程，最短只需删窗口里这 1 个（下标 5…5，值 5）。删掉后剩余和 24，正好 4 × 6，能被 6 整除，答案 1。靠「余数 = target 的最近前缀」一遍扫描就找到了。
⚠️ 容易写错的地方
✗ 错：取模出现负数直接用
✓ 对：负余数 ((v%p)+p)%p 归正
prefix − need 可能为负，不归正会查错桶
✗ 错：哈希里存最早下标
✓ 对：存最近下标
求最短要配最近同余前缀（求最长才存最早）
✗ 错：漏掉两个边界判断
✓ 对：need==0 返回 0；ans==n 返回 −1
本就整除不用删；不许删整段
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
need = sum(nums) % p
if need == 0:
return 0
last = {0: -1}
prefix = 0
ans = len(nums)
for i, x in enumerate(nums):
prefix = (prefix + x) % p
target = (prefix - need) % p
if target in last:
ans = min(ans, i - last[target])
last[prefix] = i
return -1 if ans == len(nums) else ansC++
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
long long total = 0;
for (int x : nums) total = (total + x) % p;
int need = (int)total;
if (need == 0) return 0;
unordered_map<int,int> last;
last[0] = -1;
int prefix = 0, ans = nums.size();
for (int i = 0; i < (int)nums.size(); ++i) {
prefix = (prefix + nums[i]) % p;
int target = (prefix - need + p) % p;
if (last.count(target)) ans = min(ans, i - last[target]);
last[prefix] = i;
}
return ans == (int)nums.size() ? -1 : ans;
}
};Java
import java.util.*;
class Solution {
public int minSubarray(int[] nums, int p) {
long total = 0;
for (int x : nums) total = (total + x) % p;
int need = (int) total;
if (need == 0) return 0;
Map<Integer, Integer> last = new HashMap<>();
last.put(0, -1);
int prefix = 0, ans = nums.length;
for (int i = 0; i < nums.length; i++) {
prefix = (prefix + nums[i]) % p;
int target = (prefix - need + p) % p;
if (last.containsKey(target)) ans = Math.min(ans, i - last.get(target));
last.put(prefix, i);
}
return ans == nums.length ? -1 : ans;
}
}复杂度
时间
O(n)
一遍扫描，哈希查/插 O(1)
空间
O(min(n, p))
哈希表最多存 p 个不同余数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使数组和能被 P 整除 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和 LC523/525「前缀和取模 / 等量」有什么共性和区别？+
共性都是「前缀和（取模）+ 哈希」把子数组条件转成「两端前缀同余 / 相等」。区别在存什么:这题求最短删除，存余数的最近下标；LC525 求最长，存最早下标；LC523 判存在性也要存某个出现下标（常存最早），再检查 i − j ≥ 2 保证子数组长度至少为 2，光记是否出现过不够。
为什么余数最多只有 p 种，空间能压到 O(min(n,p))？+
prefix 都对 p 取了模，取值只能是 0..p−1 共 p 个，所以哈希表里不同键最多 p 个；n 很大、p 较小时空间是 O(p)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使数组和能被 P 整除 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。