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 <= 105
1 <= nums[i] <= 109
1 <= p <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/make-sum-divisible-by-p
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

这道题首先我们得了解两个概念：

1.x mod p = 0   ——————————>   (x-y) mod p = y mod p

2.(x-y) mod p = z   ——————————>   y mod p = (x-z) mod p

首先，我们先将所有元素加起来，往后跟p取余，如果等于0，那么证明这个不用删除元素，直接返回0即可。

其次，如果和p取余后不等于0，那么我们就将这个当做是一个目标余数，简单来说，就是我们找到最短的一个子序列，往后等于这个目标余数即可。

最后，代码使用了一个无序映射（unordered map），存储累加和除以 p 的余数和对应的下标。代码通过遍历数组，累加数组元素，计算当前累加和减去目标余数再加上 p 的余数，然后取该值与 p 的余数，得到的结果就是当前累加和中要找到的目标余数。如果在无序映射中找到了相同的目标余数，则表示在当前下标之前的子数组中存在和为目标余数的子数组，此时更新 n 的值为当前下标减去在无序映射中找到的目标余数对应的下标，即得到以当前下标为结尾的和为目标余数的最小子数组长度。如果遍历完整个数组后，n 的值没有被更新，则说明无法找到和为目标余数的子数组，返回 -1。否则，返回 n 的值即可。

代码：

class Solution {
public:int minSubarray(vector& nums, int p) {long long sum1 = 0;for(int a : nums)sum1 += a;long target = sum1 % p;if(target == 0)return 0;unordered_map mid{{0,0}};int index = 0;int n = nums.size();long sum2 = 0;for(int a : nums){sum2 += a;index++;int x = (sum2 - target + p) % p;if(mid.count(x))n = min(n,index-mid[x]);mid[sum2 % p] = index;}if(n == nums.size())return -1;return n;}
};