题目描述

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

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

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

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

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

算法

(前缀和，哈希表) $O(n)$

1. 先求出数组整体的和 $tot$。如果 $tot$ 本身能被 $p$ 整除，返回 0。
2. 定义哈希表记录当前位置之前的所有前缀和模 $p$ 后所对应的最大位置。
3. 对于当前前缀和 $sum$，求出需要从当前前缀中保留多少才能使得剩余的部分能被 $p$ 整除。定义 $r := (p - (tot - sum) \text{%} p) \text{%} p$。
4. 如果在哈希表中发现了 $r$，则说明可以保留部分前缀，然后需要去掉的部分的长度为 $i - mp(r)$。
5. 最后如果发现需要去掉全部数组，返回 -1。

时间复杂度

• 遍历数组常数次，哈希表的单次操作时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        const int n = nums.size();
        LL tot = 0;
        for (int i = 0; i < n; i++)
            tot += nums[i];

        if (tot % p == 0)
            return 0;

        LL sum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;

        int ans = n;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            int r = (p - (tot - sum) % p) % p;

            if (mp.find(r) != mp.end())
                ans = min(ans, i - mp[r]);

            mp[sum % p] = i;
        }

        if (ans == n)
            ans = -1;
        return ans;
    }
};