2023-03-10 LeetCode：1590. 使数组和能被

问题链接

1590. 使数组和能被 P 整除

问题描述

给你一个正整数数组 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 。

前置知识：前缀和

假设数组[3,1,4,2]，前缀和就是用一个长度为5的数组来表示，前缀和数组的第n位表示：原数组第1位到第n位的累加。
注意：前缀和数组的第0位为0。

解题思路

核心思路：前缀和

1. 我们先遍历数组求和，并对p取模，算出需要去掉的数，记为m;
2. 再次遍历数组，一边求前缀和，一边寻找前面的前缀和是否有满足这样条件的：等于 当前前缀和减m加上p并p取模的。

代码示例（JAVA）

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

        int min = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        int currentM = 0;
        for (int i = 0; i < nums.length; i++) {
            map.put(currentM, i);
            currentM = (nums[i] + currentM) % p;
            if (map.containsKey((currentM - m + p) % p)) {
                min = Math.min(min, i - map.get((currentM - m + p) % p) + 1);
            }
        }
        
        return min == nums.length ? -1 : min;
    }
}

时间复杂度：O(n)