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

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 哈希表 前缀和

题目描述

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

image-20260929085324217

image-20260929085324343

题意分析

删除一段最短的连续子数组，使剩余元素之和能被 p 整除。可以删除空数组，也就是不做删除，但不能把整个数组删掉；没有合法方案时返回 -1。

设全数组和对 p 的余数为 target。剩余和等于“总和减去被删部分”，因此被删部分的余数必须也等于 target。问题转为寻找余数满足条件的最短连续区间。

解法：前缀和 + 哈希表

核心思路

[!blue]

先计算总余数；若 target == 0，不删除已经最优，直接返回 0。否则从左到右枚举被删区间的右端点 i，用 prefix 保存 nums[0..i] 的前缀余数。

若删去 [j + 1, i]，它的余数来自当前前缀减去截至 j 的历史前缀。要求这个差与 target 模 p 同余，就需要历史前缀余数为 (prefix - target + p) % p。加上 p 是为了把可能的负差调整到统一的 0..p - 1 范围。

用 latest 记录每种余数最近出现的下标。固定右端点时，满足条件的历史下标 j 越大，长度 i - j 越短；对以后的右端点也一样，因此新的同余前缀可以直接覆盖旧记录。

初始化 latest[0] = -1，表示数组开始前的空前缀，这样从下标 0 开始删除也能统一计算。先查询历史记录，再登记当前位置，始终用过去的前缀作为区间左边界。最短长度初始为 n，最后只有严格小于 n 的结果才能接受。

解题步骤

  1. 每加入一个元素就取模，计算全数组余数 target；若为 0，返回 0。
  2. 创建余数到最近下标的映射，登记空前缀 0 → -1，令 best = n。
  3. 遍历下标 i，更新当前前缀余数，并计算所需历史余数 need。
  4. 若映射中存在 need，用 i - previous 更新最短长度；随后将当前余数的位置覆盖为 i。
  5. 若 best 仍为 n，说明没有找到允许的更短删除区间，返回 -1；否则返回 best。

代码实现

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+1,p))$，保存已出现余数的最近位置。

关键点总结

[!green]

  • 需要抵消的是全数组余数，被删区间本身不一定能被 p 整除。
  • 同余前缀中最近的位置始终给出更短区间，可以永久替代更早位置。
  • 空前缀统一处理从数组开头删除的情况，最终长度判断排除整段删除。
  • 全程只保存余数，不必构造可能很大的完整前缀和。

易错点总结

[!yellow]

  • 总余数为 0 时应直接返回 0，不用寻找非空删除区间。
  • 保留某种余数第一次出现的位置会错过更短答案，这里需要不断覆盖为最新下标。
  • 直接用 prefix - target 查表，可能得到与表中规范余数不同的负值，需要补 p 再取模。
  • 删除全数组虽然能留下和为零的空数组，但题目明确禁止，长度为 n 必须返回 -1。
  • 不要用 int 直接累计完整总和；代码每次加完就取模，中间加法在当前元素和 p 的范围内不会溢出。

相似题目

题目 难度 关联与区别
974. 和可被 K 整除的子数组 中等 同样按前缀余数匹配，本题要删掉余数等于全数组余数的最短区间，而不是统计余数0的区间。
325. 和等于 k 的最长子数组长度 中等 原题求最长时保留最早前缀位置，本题求最短时应保留最近位置。
523. 连续的子数组和 中等 按前缀和余数分类；本题查找应删区间的余数差并最小化长度，该题寻找相同余数且距离至少为二的前缀。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/86019240
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！