题目描述

给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1。

例如：nums = [3,1,4,2]，p = 6，输出 1。

解释：数组总和为 3+1+4+2=10，10 % 6 = 4。我们需要移除一个和为 4 的子数组。移除子数组 [4]（索引 2），剩余元素和 3+1+2=6，能被 6 整除。子数组长度为 1，是最短的。

解题思路

核心数学原理

设数组总和模 p 的值为 totalSum % p = target：

  • 如果 target == 0，说明整个数组的和已经能被 p 整除，直接返回 0。
  • 否则，我们需要移除一个子数组，使得该子数组的和模 p 等于 target，这样剩余元素的和模 p 就等于 0。

为什么？ 因为剩余和 = 总和 - 子数组和。若剩余和能被 p 整除，即 (totalSum - subSum) % p == 0，则 subSum % p == totalSum % p == target。

前缀和 + 哈希表

问题转化为：寻找最短的连续子数组，其和模 p 等于 target。

设 prefix[i] 为 nums[0..i] 的前缀和模 p。如果存在 j < i 使得 (prefix[i] - prefix[j]) % p == target，则子数组 nums[j+1..i] 满足条件。

即我们需要 prefix[j] == (prefix[i] - target) % p（注意处理负数取模）。

算法步骤：

  1. 计算 totalSum % p 得到 target。如果为 0，返回 0。
  2. 使用哈希表 map 记录每个前缀和模值最后一次出现的位置（或第一次出现的位置），初始化 map.put(0, -1)。
  3. 遍历数组，维护当前前缀和模值 curSum：
    • 计算需要的值 needed = (curSum - target + p) % p。
    • 如果 map 中存在 needed，说明找到了符合条件的子数组 [map.get(needed)+1, i]，更新最小长度。
    • 将 (curSum, i) 存入 map（记录当前位置，确保能找到最短子数组）。
  4. 返回最小长度，若为 n 则返回 -1。

示例说明

以 nums = [3,1,4,2]，p = 6 为例：

  • totalSum = 10，target = 4
  • map = {0: -1}，curSum = 0
  • i=0（3）：curSum = 3，needed = (3-4+6)%6 = 5，不在 map；map = {0:-1, 3:0}
  • i=1（1）：curSum = 4，needed = (4-4+6)%6 = 0，在 map（位置 -1）→ 长度 = 1-(-1) = 2；map = {0:-1, 3:0, 4:1}
  • i=2（4）：curSum = 2，needed = (2-4+6)%6 = 4，在 map（位置 1）→ 长度 = 2-1 = 1，更新 minLen = 1；map = {…, 2:2}
  • i=3（2）：curSum = 4，needed = 0，在 map（位置 -1）→ 长度 = 3-(-1) = 4；minLen = 1
  • 返回 1

复杂度分析

  • 时间复杂度：O(n)，一次遍历完成。
  • 空间复杂度：O(n)，哈希表最多存储 n 个前缀和模值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package code.J1590;

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

public class J1590 {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int totalSum = 0;
        for (int num : nums) {
            totalSum = (totalSum + num) % p;
        }
        int target = totalSum;
        if (target == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int curSum = 0;
        int minLen = n;
        for (int i = 0; i < n; i++) {
            curSum = (curSum + nums[i]) % p;
            int needed = (curSum - target + p) % p;
            if (map.containsKey(needed)) {
                minLen = Math.min(minLen, i - map.get(needed));
            }
            map.put(curSum, i);
        }
        return minLen == n ? -1 : minLen;
    }
}