2875. Minimum Size Subarray in Infinite Array
You are given a 0-indexed array nums and an integer target.
A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.
Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
vector<long long> pre;
unordered_map<long long, long long> mp;
for(auto& n : nums) {
pre.push_back((pre.size() ? pre.back() : 0) + n);
mp[pre.back()] = pre.size() - 1;
}
long long tot = pre.back(), res = INT_MAX;
for(auto& n : nums) {
pre.push_back((pre.size() ? pre.back() : 0) + n);
mp[pre.back()] = pre.size() - 1;
}
for(int i = 0; i < nums.size(); i++) {
long long loop = target / tot * nums.size();
long long x = target % tot;
if(mp.count(pre[i] + x)) {
res = min(res, loop + mp[pre[i] + x] - i);
}
}
return res == INT_MAX ? -1 : res;
}
};
|
