Description#
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.
Example 1:
Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.
Example 2:
Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.
Example 3:
Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= target <= 109
Solutions#
Solution 1: Prefix Sum + Hash Table#
First, we calculate the sum of all elements in the array $nums$, denoted as $s$.
If $target \gt s$, we can reduce $target$ to the range $[0, s)$ by subtracting $\lfloor \frac{target}{s} \rfloor \times s$ from it. Then, the length of the subarray is $a = \lfloor \frac{target}{s} \rfloor \times n$, where $n$ is the length of the array $nums$.
Next, we need to find the shortest subarray in $nums$ whose sum equals $target$, or the shortest subarray whose prefix sum plus suffix sum equals $s - target$. We can use prefix sum and a hash table to find such subarrays.
If we find such a subarray, the final answer is $a + b$. Otherwise, the answer is $-1$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where n is the length of the array $nums$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def minSizeSubarray(self, nums: List[int], target: int) -> int:
s = sum(nums)
n = len(nums)
a = 0
if target > s:
a = n * (target // s)
target -= target // s * s
if target == s:
return n
pos = {0: -1}
pre = 0
b = inf
for i, x in enumerate(nums):
pre += x
if (t := pre - target) in pos:
b = min(b, i - pos[t])
if (t := pre - (s - target)) in pos:
b = min(b, n - (i - pos[t]))
pos[pre] = i
return -1 if b == inf else a + b
|
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
26
27
28
29
| class Solution {
public int minSizeSubarray(int[] nums, int target) {
long s = Arrays.stream(nums).sum();
int n = nums.length;
int a = 0;
if (target > s) {
a = n * (target / (int) s);
target -= target / s * s;
}
if (target == s) {
return n;
}
Map<Long, Integer> pos = new HashMap<>();
pos.put(0L, -1);
long pre = 0;
int b = 1 << 30;
for (int i = 0; i < n; ++i) {
pre += nums[i];
if (pos.containsKey(pre - target)) {
b = Math.min(b, i - pos.get(pre - target));
}
if (pos.containsKey(pre - (s - target))) {
b = Math.min(b, n - (i - pos.get(pre - (s - target))));
}
pos.put(pre, i);
}
return b == 1 << 30 ? -1 : a + b;
}
}
|
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
26
27
28
29
| class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
long long s = accumulate(nums.begin(), nums.end(), 0LL);
int n = nums.size();
int a = 0;
if (target > s) {
a = n * (target / s);
target -= target / s * s;
}
if (target == s) {
return n;
}
unordered_map<int, int> pos{{0, -1}};
long long pre = 0;
int b = 1 << 30;
for (int i = 0; i < n; ++i) {
pre += nums[i];
if (pos.count(pre - target)) {
b = min(b, i - pos[pre - target]);
}
if (pos.count(pre - (s - target))) {
b = min(b, n - (i - pos[pre - (s - target)]));
}
pos[pre] = i;
}
return b == 1 << 30 ? -1 : a + b;
}
};
|
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
26
27
28
29
30
31
32
| func minSizeSubarray(nums []int, target int) int {
s := 0
for _, x := range nums {
s += x
}
n := len(nums)
a := 0
if target > s {
a = n * (target / s)
target -= target / s * s
}
if target == s {
return n
}
pos := map[int]int{0: -1}
pre := 0
b := 1 << 30
for i, x := range nums {
pre += x
if j, ok := pos[pre-target]; ok {
b = min(b, i-j)
}
if j, ok := pos[pre-(s-target)]; ok {
b = min(b, n-(i-j))
}
pos[pre] = i
}
if b == 1<<30 {
return -1
}
return a + b
}
|
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
26
27
| function minSizeSubarray(nums: number[], target: number): number {
const s = nums.reduce((a, b) => a + b);
const n = nums.length;
let a = 0;
if (target > s) {
a = n * ((target / s) | 0);
target -= ((target / s) | 0) * s;
}
if (target === s) {
return n;
}
const pos: Map<number, number> = new Map();
let pre = 0;
pos.set(0, -1);
let b = Infinity;
for (let i = 0; i < n; ++i) {
pre += nums[i];
if (pos.has(pre - target)) {
b = Math.min(b, i - pos.get(pre - target)!);
}
if (pos.has(pre - (s - target))) {
b = Math.min(b, n - (i - pos.get(pre - (s - target))!));
}
pos.set(pre, i);
}
return b === Infinity ? -1 : a + b;
}
|
Solution 2#
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
int minLength = n * 2 + 1;
int l = 0;
int sum = 0;
for (int r = 0; r < n * 2; r++) {
int start = l % n;
int end = r % n;
sum += nums[end];
while (sum > k && l <= r) {
start = l % n;
sum -= nums[start];
l++;
}
if (sum == k) {
minLength = Math.min(minLength, r - l + 1);
start = l % n;
sum -= nums[start];
l++;
}
}
return minLength == n * 2 + 1 ? -1 : minLength;
}
public int minSizeSubarray(int[] nums, int target) {
int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
int k = target % sum;
int ans = target / sum * n;
if (k == 0) {
return ans;
}
int res = shortestSubarray(nums, k);
return res == -1 ? -1 : ans + res;
}
}
|
