题目名称

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

题解

采用了前缀和和求余。

定理一：给定正整数 x、y、z、p，如果 y mod p = x，那么 (y−z) mod p=0等价于 z mod p=x。

定理二：给定正整数 x，y，z，p，那么 (y−z) mod p=x 等价于 z mod p=(y−x) mod p。

首先根据题意，如果所有的和求余后为0的话则说明不需要去除任何子数组，所以返回 0

然后首先计算出 数组所有元素和 与 P 的余数 reduce

然后计算数组每一位与前面所有元素的和 与 p 的余数，然后将当前 index 添加到 map数组中。具体参考下方代码

答案

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
30
31
32
/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
// 前缀和，如果求出的值的范围内包含拥有相同的余数，则可以去最后的一个余数
var minSubarray = function(nums, p) {
  let total = nums.reduce((total, item) => total = (total + item) % p, 0) // 求余的原因是为了避免求得的和的长度超过了32位，无法正常获取值
  if(total === 0) return 0
  let reduce = total % p
  let t = 0, index = new Map();
  if(nums.some(item => item % p === reduce)) return 1
  let min = nums.length
  for(let i = 0; i < nums.length; i++) {
    let redu = t % p
    index.set(redu, i) // 使用map 设置当前余数的最近的一个位置
    t = (t + nums[i]) % p
    // t % p = (redu + reduce) % p => 求互补的两个余数，这两个余数相加，刚好余p之后还剩个 reduce，也就代表这一块的内容可以删除
    // (t - reduce) % p = redu % p =>
    // (t - reduce + p) % p = redu % p 负数进行取余时，余数为负数，因此计算 时需要加上 p
    if(index.has((t - reduce + p) % p )) { // 判断当前的和的余数是否与存在于map中， +p 的原因是为了避免 - reduce 后得到负数
      min = Math.min(min, i - index.get((t - reduce + p) % p) + 1) // 如果当前求得的余数正好存在map 对象里面
    }
  }
  return min === nums.length ? -1 : min
};

console.log(minSubarray([3,1,4,2], 6), "1")
console.log(minSubarray([6,3,5,2], 9), "2")
console.log(minSubarray([1,2,3], 3), "0")
console.log(minSubarray([4,4,2], 7), "-1")
console.log(minSubarray([26,19,11,14,18,4,7,1,30,23,19,8,10,6,26,3], 26), "3")