题目描述

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

样例

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109

算法分析

思路源于： AcWing 1230. K倍区间

某一段连续的区间是 $p$ 的倍数有关，一般都利用数组的前缀和取模做分析

推理过程：

已知 $(nums[1] + nums[2] + … + nums[n]) \% p = x$

取任意连续的区间 $[L + 1,R]$ 使得剩下的区间的累加和是 $p$ 的倍数，

等价于 $(nums[1] + nums[2] + … + nums[L] + nums[R + 1] + … + nums[n]) \% p = 0 $

等价于找到 $L$ 和 $R$ 使得 $(nums[L + 1] + nums[l + 2] + … + nums[R]) \% p = x $

操作过程

计算出 $nums[]$ 数组的前缀和，分别枚举 $L$ 和 $R$ ，使得$(s[R] - s[L]) % p = (nums[L + 1] + … + nums[R]) \% p$ 即可，由于给的数据范围是 $10^5$ ，因此不能用两重循环解决

用哈希表存储 之前枚举过的前缀和取模后的值最晚出现的位置，当枚举到 $R$ 时，$ (nums[1] + nums[2] + … + nums[R]) \% p = a $，只需要判断是否能在哈希表中找到 $L$ ，使得 $(nums[1] + nums[2] + … + nums[L]) \% p = (a - x) \% p$ 即可，这样只需要一重循环就可以解决

时间复杂度 $O(n)$

参考文献

胡图图

Java 代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0;i < n;i ++) sum = (sum + nums[i]) % p;
        if(sum == 0) return 0;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);

        int res = n;
        for(int i = 0, s = 0;i < n;i ++)
        {
            s = (s + nums[i]) % p;
            int t = ((s - sum) % p + p) % p;
            if(map.containsKey(t)) res = Math.min(res, i - map.get(t));
            map.put(s, i);
        }
        if(res == n) return -1;
        return res;
    }
}