# 1590.使数组和能被 P 整除 (Medium)

## 问题描述
[1590. 使数组和能被 P 整除 (Medium)](https://leetcode.cn/problems/make-sum-divisible-by-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⁹`

## 解题思路
首先维护一个前缀和数组，数组中的元素为前缀和对`p`的模，记数组所有元素对`p`的模为`mod`，那么，我们要找的就是和的模也为`mod`的子数组；

同时，我们维护一个哈希表，哈希表的`key`为前`i`个数对`p`的模，`value`为`i`；遍历前缀和数组，并更新哈希表，假设当前前缀和对`p`的模为`tmp_mod`，则查找哈希表中是否存在`(tmp_mod - mod + p) % p`的元素，`res = std::min(res, ump[tmp_mod] - ump[(tmp_mod - mod + p) % p])`。

哈希表的值是遍历前缀和数组过程中，相同模的过程中的最大的`i`。

## 代码
```cpp
class Solution {
  public:
    int minSubarray(vector<int> &nums, int p) {
        int n = nums.size();
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = (prefix[i - 1] + nums[i - 1]) % p; // 防止爆int
        }
        int mod = prefix[n] % p;
        if (mod == 0) {
            return 0;
        }
        unordered_map<int, int> ump;
        ump[0] = 0;
        int res = n;
        for (int i = 1; i <= n; ++i) {
            int tmp_mod = prefix[i] % p;
            ump[tmp_mod] = i;
            if (ump.find((tmp_mod - mod + p) % p) != ump.end()) {
                res = std::min(res, i - ump[(tmp_mod - mod + p) % p]);
            }
        }
        if (res == n) {
            return -1;
        }
        return res;
    }
};
```