题目链接
题目描述
n
u
nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被
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
s
.
l
n
≤
1
0
5
1≤nums.length≤105 -
1
≤
n
u
s
[
]
≤
1
0
9
1≤nums[i]≤109 -
1
≤
p
≤
1
0
9
1 leq p leq 10^9
1≤p≤109
解法：前缀和 + 哈希表
n
u
s
nums
nums 的和为
s
s
s，那么
=
s
m
o
p
- 如果
=
0
k = 0
k=0，说明整个数组的和都可以被p
p
p 整除，所以不需要移除元素，直接返回0
0
0； - 如果
≠
0
k neq 0
k=0，假设我们需要移除的这个子数组和为
t，那么t
m
o
p
=
k
t mod p = k
t mod p=k，并且还要要求这个子数组的长度是最短的。
[
j
,
]
[j,i]
s
u
m
sum 表示
n
u
m
s
nums
nums 的前缀和，即：
(
s
u
m
[
i
]
−
s
u
m
[
j
−
1
]
)
m
o
p
=
k
(sum[i]−sum[j−1]) mod p=k
再转换一下：
s
u
m
[
j
−
1
]
m
o
p
=
s
u
m
[
i
]
m
o
d
p
−
k
sum[j-1] mod p = sum[i] mod p – k
sum[j−1] mod p=sum[i] mod p−k
由于
s
u
m
[
j
]
m
o
d
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−k+p) mod p
s
u
m
[
i
]
m
o
d
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−k+p) mod p，如果对于当前
k
e
y
key，哈希表
m
p
mp 中有记录，则
j
=
m
p
[
k
e
y
]
j=mp[key]。说明移除此时的子数组
[
j
,
i
]
[j,i]
[j,i] 就能使
n
u
m
s
nums
n
s
ans
ans。
注意：
O
(
n
)
O(n)
O(n)
C++代码：
using LL = long long;
class Solution {
public:
int minSubarray(vector<int>& 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_map<int,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;
}
};
原文地址:https://blog.csdn.net/m0_74396439/article/details/134629697
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_14583.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
