跳到主要内容

1590.使数组和能被 P 整除

· 阅读需 4 分钟

1、题干​

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

前缀和，我是真的前了
哈希表，我是真的哈了
模运算，我模xxxxxxxxx了

2、思路​

先求 nums 前缀和数组 sums，数组总和 sum，总和与 p 的余数 mod，然后讨论几种情况:

  • 无需剔除：如果 mod 为 0，返回 0
  • 剔除1个：如果剔除 nums 中某个数能整除，返回 1
  • 剔除尾部：如果 sums[i] 能整除 p，nums.length - i - 1 作为备选答案
  • 剔除头部：如果 sums[i] % p === mod，i+1 作为备选答案
  • 剔除中间：如果存在下标 i 和 j 且 sums[j] % p ===(sums[i] % p + p - mod) % p，i-j 作为备选答案

真是不知道写了个什么妖魔鬼怪

3、代码​

function minSubarray(nums: number[], p: number): number {
    const sums = [...nums];
    for (let i = 1; i < sums.length; i++) {
        sums[i] += sums[i - 1];
    }

    const sum = sums.at(-1), mod = sum % p;
    if (!mod) return 0;

    let ans = nums.length;
    const map = new Map();
    for (let i = 0; i < sums.length; i++) {
        if ((sum - nums[i]) % p === 0) return 1;

        const m = sums[i] % p;
        if (m === 0) ans = Math.min(nums.length - i - 1, ans);
        else if (m === mod) ans = Math.min(i + 1, ans);
        else {
            const sm = (m + p - mod) % p;
            if (map.has(sm)) ans = Math.min(i - map.get(sm), ans);
        }

        map.set(m, i);
    }

    return ans === nums.length ? -1 : ans;
}

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png