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

1590. 使数组和能被 P 整除

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

思路

1. 通过遍历nums得到总的sum，顺便将前缀和保存
2. 计算得到整个 nums的mod
3. 再次对nums遍历，寻找左边的子数组需要删除的部分
4. 首先确定目标值是否存在于map中
   1. 如果不存在，将以 prefixSum[i] % p : index保存
   2. 如果存在，判断当前下标和找到的下标之间的距离，更新最小长度
5. 返回最小长度

代码

var minSubarray = function(nums, p) {
  const prefixSum = [];
  let sum = 0, len = nums.length;
  for(let i = 0; i <= len; i++) {
    prefixSum.push(sum);
    if (nums[i]) {
      sum += nums[i];
    }
  }
  
  const mod = sum % p;
  if (mod === 0) return 0;

  const map = new Map();
  let min = len;

  for(let i = 0; i <= len; i++) {
    const val = (prefixSum[i] - mod) % p;
    if (map.has(val)) {
      min = Math.min(min, i - map.get(val))
    }
    map.set(prefixSum[i] % p, i);
  }
  return min === len ? -1 : min;
};

复杂度分析

时间复杂度 $O(N)$

空间复杂度 $O(N)$