前置知识
模运算的世界：当加减乘除遇上取模
提示 1
例如 $\textit{nums}=[11,2,5,7,8,9]$，$p=10$，那么把 $[5,7]$ 去掉，剩余的数字相加等于 $30$，可以被 $p$ 整除。
所有元素的和 $42\bmod 10=2$，而 $(5+7)\bmod 10$ 也等于 $2$。
设所有元素的和为 $x$，去掉的元素和为 $y$。要使 $x-y$ 能被 $p$ 整除，根据前置知识中同余的定义，这等价于满足
$$
y \equiv x \pmod p
$$
提示 2
把 $y$ 用 前缀和 表示，问题转换成：在前缀和数组上找到两个数 $s[\textit{left}]$ 和 $s[\textit{right}]$，满足 $\textit{right}-\textit{left}$ 最小且
$$
s[\textit{right}]-s[\textit{left}]\equiv x \pmod p
$$
根据前置知识，将上式移项，得
$$
s[\textit{right}]-x \equiv s[\textit{left}]\pmod p
$$
上式相当于
$$
((s[\textit{right}]-x)\bmod p+p)\bmod p= s[\textit{left}]\bmod p
$$
也可以写成
$$
(s[\textit{right}]\bmod p-x\bmod p+p)\bmod p= s[\textit{left}]\bmod p
$$
提示 3
遍历 $s$ 的同时，用哈希表 $\textit{last}$ 记录 $s[i]\bmod p$ 最近一次出现的下标，如果 $\textit{last}$ 中包含 $(s[i]\bmod p-x\bmod p+p)\bmod p$，设其对应的下标为 $j$，那么 $[j,i)$ 是一个符合题目要求的子数组。
⚠注意：本题可以移除空子数组，所以要先更新 $\textit{last}$，再更新答案。
枚举所有 $i$，计算符合要求的子数组长度的最小值，就是答案。如果没有符合要求的子数组，则返回 $-1$。
代码实现时，可以把答案初始化成 $\textit{nums}$ 的长度 $n$。如果最后答案等于 $n$，则表示没有符合要求的子数组，因为题目不允许将整个数组都移除。
答疑
问：为什么不能用双指针（不定长滑动窗口）做？
答：使用双指针需要满足单调性，但是 $s[i]\bmod p$ 并不是单调的，所以不能用双指针。具体请看【基础算法精讲 03】。
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
s = list(accumulate(nums, initial=0))
x = s[-1] % p
if x == 0:
return 0 # 移除空子数组（这行可以不要）
ans = n = len(nums)
last = {}
for i, v in enumerate(s):
last[v % p] = i
j = last.get((v - x) % p, -n) # 如果不存在，-n 可以保证 i-j >= n
ans = min(ans, i - j)
return ans if ans < n else -1
class Solution {
public int minSubarray(int[] nums, int p) {
int n = nums.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; i++) {
s[i + 1] = (s[i] + nums[i]) % p;
}
int x = s[n];
if (x == 0) {
return 0; // 移除空子数组（这行可以不要）
}
int ans = n;
Map<Integer, Integer> last = new HashMap<>();
for (int i = 0; i <= n; i++) {
last.put(s[i], i);
// 如果不存在，-n 可以保证 i-j >= n
int j = last.getOrDefault((s[i] - x + p) % p, -n);
ans = Math.min(ans, i - j);
}
return ans < n ? ans : -1;
}
}
class Solution {
public:
int minSubarray(vector<int> &nums, int p) {
int n = nums.size(), s[n + 1];
s[0] = 0;
for (int i = 0; i < n; i++) {
s[i + 1] = (s[i] + nums[i]) % p;
}
int x = s[n];
if (x == 0) {
return 0; // 移除空子数组（这行可以不要）
}
int ans = n;
unordered_map<int, int> last;
for (int i = 0; i <= n; ++i) {
last[s[i]] = i;
auto it = last.find((s[i] - x + p) % p);
if (it != last.end()) {
ans = min(ans, i - it->second);
}
}
return ans < n ? ans : -1;
}
};
func minSubarray(nums []int, p int) int {
n := len(nums)
s := make([]int, n+1)
for i, v := range nums {
s[i+1] = (s[i] + v) % p
}
x := s[n]
if x == 0 {
return 0 // 移除空子数组（这个 if 可以不要）
}
ans := n
last := map[int]int{}
for i, v := range s {
last[v] = i
if j, ok := last[(v-x+p)%p]; ok {
ans = min(ans, i-j)
}
}
if ans < n {
return ans
}
return -1
}
也可以不用前缀和数组，一边遍历 $\textit{nums}$ 一边计算前缀和。
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
x = sum(nums) % p
if x == 0:
return 0 # 移除空子数组（这行可以不要）
ans = n = len(nums)
s = 0
last = {s: -1} # 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
for i, v in enumerate(nums):
s += v
last[s % p] = i
j = last.get((s - x) % p, -n) # 如果不存在，-n 可以保证 i-j >= n
ans = min(ans, i - j) # 改成手写 min 会再快一些
return ans if ans < n else -1
class Solution {
public int minSubarray(int[] nums, int p) {
long t = 0;
for (int v : nums) {
t += v;
}
int x = (int) (t % p);
if (x == 0) {
return 0; // 移除空子数组（这行可以不要）
}
int n = nums.length;
int ans = n;
int s = 0;
Map<Integer, Integer> last = new HashMap<>();
last.put(s, -1); // 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
for (int i = 0; i < n; i++) {
s = (s + nums[i]) % p;
last.put(s, i);
// 如果不存在，-n 可以保证 i-j >= n
int j = last.getOrDefault((s - x + p) % p, -n);
ans = Math.min(ans, i - j);
}
return ans < n ? ans : -1;
}
}
class Solution {
public:
int minSubarray(vector<int> &nums, int p) {
int x = reduce(nums.begin(), nums.end(), 0LL) % p;
if (x == 0) {
return 0; // 移除空子数组（这行可以不要）
}
int n = nums.size(), ans = n, s = 0;
// 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
unordered_map<int, int> last{{s, -1}};
for (int i = 0; i < n; i++) {
s = (s + nums[i]) % p;
last[s] = i;
auto it = last.find((s - x + p) % p);
if (it != last.end()) {
ans = min(ans, i - it->second);
}
}
return ans < n ? ans : -1;
}
};
func minSubarray(nums []int, p int) int {
x := 0
for _, v := range nums {
x += v
}
x %= p
if x == 0 {
return 0 // 移除空子数组（这个 if 可以不要）
}
n := len(nums)
ans, s := n, 0
// 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
last := map[int]int{s: -1}
for i, v := range nums {
s += v
last[s%p] = i
if j, ok := last[(s-x+p)%p]; ok {
ans = min(ans, i-j)
}
}
if ans < n {
return ans
}
return -1
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录