莱芜网站建设公司,在线做图网站,通用cms网站,桂林小程序开发定制题目链接 Leetcode.1590 使数组和能被 P 整除 rating : 2039 题目描述
给你一个正整数数组 n u m s nums nums#xff0c;请你移除 最短 子数组#xff08;可以为 空#xff09;#xff0c;使得剩余元素的 和 能被 p p p 整除。 不允许 将整个数组都移除。
请你返回你需…题目链接 Leetcode.1590 使数组和能被 P 整除 rating : 2039 题目描述
给你一个正整数数组 n u m s nums nums请你移除 最短 子数组可以为 空使得剩余元素的 和 能被 p p p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度如果无法满足题目要求返回 − 1 -1 −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 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \leq nums[i] \leq 10^9 1≤nums[i]≤109 1 ≤ p ≤ 1 0 9 1 \leq p \leq 10^9 1≤p≤109
解法前缀和 哈希表
假设整个数组 n u m s nums nums 的和为 s s s那么 k s m o d p k s\ mod\ p ks mod p。
如果 k 0 k 0 k0说明整个数组的和都可以被 p p p 整除所以不需要移除元素直接返回 0 0 0如果 k ≠ 0 k \neq 0 k0假设我们需要移除的这个子数组和为 t t t那么 t m o d p k t\ mod\ p k t mod pk并且还要要求这个子数组的长度是最短的。
假设区间 [ j , i ] [j,i] [j,i] 的子数组满足这个条件我们用 s u m sum sum 表示 n u m s nums nums 的前缀和即 ( s u m [ i ] − s u m [ j − 1 ] ) m o d p k (sum[i] - sum[j-1])\ mod\ p k (sum[i]−sum[j−1]) mod pk
再转换一下 s u m [ j − 1 ] m o d p s u m [ i ] m o d p − k sum[j-1]\ mod\ p sum[i]\ mod\ p - k sum[j−1] mod psum[i] mod p−k
由于 s u m [ j ] m o d p − k sum[j]\ mod\ p - k sum[j] mod p−k 有可能是负数所以我们需要再将其转换为整数 s u m [ j − 1 ] m o d p ( s u m [ i ] m o d p − k p ) m o d p sum[j-1]\ mod\ p (sum[i]\ mod\ p - k p)\ mod\ p sum[j−1] mod p(sum[i] mod p−kp) mod p
我们用哈希表来记录这个 s u m [ i ] m o d p sum[i]\ mod\ p sum[i] mod p值就是其对应的下标 i i i。
我们令 k e y ( s u m [ i ] m o d p − k p ) m o d p key (sum[i]\ mod\ p - k p)\ mod\ p key(sum[i] mod p−kp) mod p如果对于当前 k e y key key哈希表 m p mp mp 中有记录则 j m p [ k e y ] j mp[key] jmp[key]。说明移除此时的子数组 [ j , i ] [j,i] [j,i] 就能使 n u m s nums nums 的剩余元素满足条件那么我们更新答案 a n s ans ans。
注意
哈希表 m p mp mp 初始时需要加入 { 0 , − 1 } \{0 , -1 \} {0,−1} a n s ans ans 是最终的答案需要移除的最短子数组的长度初始化为一个较大的数即可
时间复杂度 O ( n ) O(n) O(n)
C代码
using LL long long;class Solution {
public:int minSubarray(vectorint nums, int p) {int n nums.size();LL sum 0;for(auto x:nums) sum x;int k sum % p;if(k 0) return 0;unordered_mapint,int mp{{0 , -1}};int ans n;sum 0;for(int i 0;i n;i){sum nums[i];auto key (sum % p - k p)%p;if(mp.find(key) ! mp.end()){auto j mp[key];ans min(ans , i - j);}mp[sum % p] i;}return ans n ? -1 : ans;}
};
