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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= p <= 10⁹

解法

方法一：前缀和 + 哈希表

我们可以先求出数组 \(\textit{nums}\) 所有元素之和模 \(p\) 的值，记为 \(k\)。如果 \(k\) 为 \(0\)，说明数组 \(\textit{nums}\) 所有元素之和就是 \(p\) 的倍数，直接返回 \(0\) 即可。

如果 \(k\) 不为 \(0\)，我们需要找到一个最短的子数组，使得删除该子数组后，剩余元素之和模 \(p\) 的值为 \(0\)。

我们可以遍历数组 \(\textit{nums}\)，维护当前的前缀和模 \(p\) 的值，记为 \(cur\)。用哈希表 \(last\) 记录每个前缀和模 \(p\) 的值最后一次出现的位置。

如果当前存在一个以 \(\textit{nums}[i]\) 结尾的子数组，使得删除该子数组后，剩余元素之和模 \(p\) 的值为 \(0\)。也就是说，我们需要找到此前的一个前缀和模 \(p\) 的值为 \(target\) 的位置 \(j\)，使得 \((target + k - cur) \bmod p = 0\)。如果找到，我们就可以将 \(j + 1\) 到 \(i\) 这一段闭区间子数组 \(\textit{nums}[j+1,..i]\) 删除，使得剩余元素之和模 \(p\) 的值为 \(0\)。

因此，如果存在一个 \(target = (cur - k + p) \bmod p\)，那么我们可以更新答案为 \(\min(ans, i - j)\)。接下来，我们更新 \(last[cur]\) 的值为 \(i\)。继续遍历数组 \(\textit{nums}\)，直到遍历结束，即可得到答案。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScriptRustJavaScript

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        k = sum(nums) % p
        if k == 0:
            return 0
        last = {0: -1}
        cur = 0
        ans = len(nums)
        for i, x in enumerate(nums):
            cur = (cur + x) % p
            target = (cur - k + p) % p
            if target in last:
                ans = min(ans, i - last[target])
            last[cur] = i
        return -1 if ans == len(nums) else ans

class Solution {
    public int minSubarray(int[] nums, int p) {
        int k = 0;
        for (int x : nums) {
            k = (k + x) % p;
        }
        if (k == 0) {
            return 0;
        }
        Map<Integer, Integer> last = new HashMap<>();
        last.put(0, -1);
        int n = nums.length;
        int ans = n;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = (cur + nums[i]) % p;
            int target = (cur - k + p) % p;
            if (last.containsKey(target)) {
                ans = Math.min(ans, i - last.get(target));
            }
            last.put(cur, i);
        }
        return ans == n ? -1 : ans;
    }
}

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int k = 0;
        for (int& x : nums) {
            k = (k + x) % p;
        }
        if (k == 0) {
            return 0;
        }
        unordered_map<int, int> last;
        last[0] = -1;
        int n = nums.size();
        int ans = n;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = (cur + nums[i]) % p;
            int target = (cur - k + p) % p;
            if (last.count(target)) {
                ans = min(ans, i - last[target]);
            }
            last[cur] = i;
        }
        return ans == n ? -1 : ans;
    }
};

func minSubarray(nums []int, p int) int {
    k := 0
    for _, x := range nums {
        k = (k + x) % p
    }
    if k == 0 {
        return 0
    }
    last := map[int]int{0: -1}
    n := len(nums)
    ans := n
    cur := 0
    for i, x := range nums {
        cur = (cur + x) % p
        target := (cur - k + p) % p
        if j, ok := last[target]; ok {
            ans = min(ans, i-j)
        }
        last[cur] = i
    }
    if ans == n {
        return -1
    }
    return ans
}

function minSubarray(nums: number[], p: number): number {
    let k = 0;
    for (const x of nums) {
        k = (k + x) % p;
    }
    if (k === 0) {
        return 0;
    }
    const last = new Map<number, number>();
    last.set(0, -1);
    const n = nums.length;
    let ans = n;
    let cur = 0;
    for (let i = 0; i < n; ++i) {
        cur = (cur + nums[i]) % p;
        const target = (cur - k + p) % p;
        if (last.has(target)) {
            const j = last.get(target)!;
            ans = Math.min(ans, i - j);
        }
        last.set(cur, i);
    }
    return ans === n ? -1 : ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
        let mut k = 0;
        for &x in &nums {
            k = (k + x) % p;
        }
        if k == 0 {
            return 0;
        }

        let mut last = HashMap::new();
        last.insert(0, -1);
        let n = nums.len();
        let mut ans = n as i32;
        let mut cur = 0;

        for i in 0..n {
            cur = (cur + nums[i]) % p;
            let target = (cur - k + p) % p;
            if let Some(&prev_idx) = last.get(&target) {
                ans = ans.min(i as i32 - prev_idx);
            }
            last.insert(cur, i as i32);
        }

        if ans == n as i32 {
            -1
        } else {
            ans
        }
    }
}

/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minSubarray = function (nums, p) {
    let k = 0;
    for (const x of nums) {
        k = (k + x) % p;
    }
    if (k === 0) {
        return 0;
    }
    const last = new Map();
    last.set(0, -1);
    const n = nums.length;
    let ans = n;
    let cur = 0;
    for (let i = 0; i < n; ++i) {
        cur = (cur + nums[i]) % p;
        const target = (cur - k + p) % p;
        if (last.has(target)) {
            const j = last.get(target);
            ans = Math.min(ans, i - j);
        }
        last.set(cur, i);
    }
    return ans === n ? -1 : ans;
};

1590. 使数组和能被 P 整除

题目描述

解法

方法一：前缀和 + 哈希表

评论