LeetCode 1590. 使数组和能被 P 整除

2023-10-26 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1590. 使数组和能被 P 整除

题意分析

给定一个正整数数组和一个整数 p，要移除一段连续的子数组（可以不移除，但不能把整个数组都移除），使得剩下元素的和能被 p 整除。求这个被移除子数组的最短长度；如果做不到，返回 -1。

「移除一段连续区间」这个措辞把可行方案限制得很死：剩下的部分是「前缀 + 后缀」的拼接，而被移除的部分是唯一一段区间。这意味着枚举对象是区间而不是任意子集。

「不能移除整个数组」是必须单列的约束。它排除了「删光所有元素让和为 0」这个平凡解，也决定了答案的合法上界是 n - 1。

数组长度可以到 $10^5$，元素值到 $10^9$，所以总和会达到 $10^{14}$ 级别，远超 32 位。不过整个问题只关心模 p 的结果，所以从一开始就边加边取模，既避免溢出又不损失信息。

$10^5$ 的长度否决了 $O(n^2)$ 枚举区间的做法，答案必须在一次线性扫描里出来。

边界上，若总和本来就能被 p 整除，一个元素都不用删，答案是 0；若找不到任何合法区间，返回 -1。元素全为正数，但取模之后余数可以是任意值，所以不能利用单调性做双指针。

解法：前缀和 + 哈希表

核心思路

设整个数组的和除以 p 的余数为 target。若 target = 0，无需删除，答案为 0；否则，被删除子数组的和也必须模 p 等于 target，剩余部分才会整除 p。

令 prefix 为扫描到当前位置的前缀和余数。若删除区间的前一个前缀余数为 previous，则区间和余数为 (prefix - previous + p) % p。要让它等于 target，需要：

previous = (prefix - target + p) % p。

因此固定右端点后，只需在哈希表中查找需要的历史余数，不必枚举左端点。为了让区间最短，同一个余数只保留最近一次出现的位置。

哈希表初始放入 0 -> -1，表示数组开始前的空前缀。每轮先查询再记录当前余数。

不变量：处理下标 i 前，latest[r] 是余数 r 最近的历史前缀位置；处理完 i 后，best 是右端点不超过 i 的最短候选长度。

正确性：任意合法删除区间都对应一对满足上述同余式的前缀，扫描到其右端点时一定会被查询到；保留最近位置会在该右端点下产生最短区间。所有右端点都被枚举，所以 best 为全局最短。若唯一候选长度为 n，它等于删除整个数组，必须返回 -1。

解题步骤

边累加边取模，求全数组余数 target；若为 0，返回 0。

初始化 latest[0] = -1，并令 best = n。

扫描数组，更新当前前缀余数 prefix。

计算 need = (prefix - target + p) % p；若存在，使用当前位置与其最近位置之差更新 best。

用当前位置覆盖 latest[prefix]，供后续右端点使用。

若 best == n 返回 -1，否则返回 best。

对 nums = [3,1,4,2]、p = 6，总余数为 4。扫描到元素 4 时当前余数为 2，需要的历史余数为 4，它最近出现在下标 1，因此删除区间 [2,2]，长度为 1。

nums = [1,2,3]、p = 3 的总余数为 0，答案是 0；nums = [1,2,3]、p = 7 只能删除整个数组，按题意返回 -1。正数数组取模后不具备单调性，不能使用普通滑动窗口。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minSubarray(int[] nums, int p) {
        int target = 0;
        for (int num : nums) {
            target = (target + num) % p;
        }
        if (target == 0) {
            return 0;
        }

        Map<Integer, Integer> latest = new HashMap<>();
        latest.put(0, -1);
        int prefix = 0;
        int best = nums.length;

        for (int i = 0; i < nums.length; i++) {
            prefix = (prefix + nums[i]) % p;
            int need = (prefix - target + p) % p;
            Integer previous = latest.get(need);
            if (previous != null) {
                best = Math.min(best, i - previous);
            }
            latest.put(prefix, i);
        }
        return best == nums.length ? -1 : best;
    }
}

func minSubarray(nums []int, p int) int {
	target := 0
	for _, num := range nums {
		target = (target + num) % p
	}
	if target == 0 {
		return 0
	}

	latest := map[int]int{0: -1}
	prefix, best := 0, len(nums)
	for i, num := range nums {
		prefix = (prefix + num) % p
		need := (prefix - target + p) % p
		if previous, ok := latest[need]; ok && i-previous < best {
			best = i - previous
		}
		latest[prefix] = i
	}
	if best == len(nums) {
		return -1
	}
	return best
}

复杂度分析

时间复杂度：期望 $O(n)$，每个元素进行常数次哈希表操作。

空间复杂度：$O(\min(n,p))$，哈希表至多保存每种已出现的前缀余数。

关键点总结

先把“剩余和整除”转化为“删除区间的余数等于总余数”。

固定右端点后，需要的历史前缀余数可以直接计算。

求最短区间要保留余数的最近位置；求最长时通常保留首次位置。

0 -> -1 统一处理从下标 0 开始的区间，最终必须排除长度为 n 的候选。

易错点总结

没有先处理 target == 0：可能错误寻找非空区间，而最优答案应为 0。

同一余数保留首次位置：会让左端点偏左，只适合求最长区间。

忘记加 p 再取模：Java 和 Go 的负数余数仍为负，哈希查找会失败。

接受 best == n：删除整个数组被题目明确禁止。

先记录当前前缀再查询：会混淆历史前缀的语义；保持先查后写更清楚稳妥。

相似题目

题目	难度	考察点
974. 和可被 K 整除的子数组	中等	同余配对但求的是方案数，哈希表存计数而非位置
523. 连续的子数组和	中等	同余判定改为存首次出现位置，还额外要求区间长度至少为 2
560. 和为 K 的子数组	中等	配对条件是差值恰为 K 而非同余，是前缀和查表的最基础形态
1658. 将 x 减到 0 的最小操作数	中等	同样把「删两端」反转成「保留中间最长区间」，反向建模的姊妹题
525. 连续数组	中等	求最长区间，因此哈希表必须存最早位置，正好与本题的覆盖策略相反
1524. 和为奇数的子数组数目	中等	模数固定为 2，哈希表可退化成两个计数器，空间降到常数
1442. 形成两个异或相等数组的三元组数目	中等	把加法前缀换成异或前缀，配对条件变成两前缀相等