Description#
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Follow up: If you have figured out the
O(n) solution, try coding another solution of which the time complexity is
O(n log(n)).
Solutions#
Solution 1: Prefix Sum + Binary Search#
First, we preprocess the prefix sum array $s$ of the array $nums$, where $s[i]$ represents the sum of the first $i$ elements of the array $nums$. Since all elements in the array $nums$ are positive integers, the array $s$ is also monotonically increasing. Also, we initialize the answer $ans = n + 1$, where $n$ is the length of the array $nums$.
Next, we traverse the prefix sum array $s$. For each element $s[i]$, we can find the smallest index $j$ that satisfies $s[j] \geq s[i] + target$ by binary search. If $j \leq n$, it means that there exists a subarray that satisfies the condition, and we can update the answer, i.e., $ans = min(ans, j - i)$.
Finally, if $ans \leq n$, it means that there exists a subarray that satisfies the condition, return $ans$, otherwise return $0$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.
1
2
3
4
5
6
7
8
9
10
| class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
s = list(accumulate(nums, initial=0))
ans = n + 1
for i, x in enumerate(s):
j = bisect_left(s, x + target)
if j <= n:
ans = min(ans, j - i)
return ans if ans <= n else 0
|
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
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
int ans = n + 1;
for (int i = 0; i <= n; ++i) {
int j = search(s, s[i] + target);
if (j <= n) {
ans = Math.min(ans, j - i);
}
}
return ans <= n ? ans : 0;
}
private int search(long[] nums, long x) {
int l = 0, r = nums.length;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<long long> s(n + 1);
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
int ans = n + 1;
for (int i = 0; i <= n; ++i) {
int j = lower_bound(s.begin(), s.end(), s[i] + target) - s.begin();
if (j <= n) {
ans = min(ans, j - i);
}
}
return ans <= n ? ans : 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func minSubArrayLen(target int, nums []int) int {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
ans := n + 1
for i, x := range s {
j := sort.SearchInts(s, x+target)
if j <= n {
ans = min(ans, j-i)
}
}
if ans == n+1 {
return 0
}
return ans
}
|
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
| function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
let ans = n + 1;
const search = (x: number) => {
let l = 0;
let r = n + 1;
while (l < r) {
const mid = (l + r) >>> 1;
if (s[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 0; i <= n; ++i) {
const j = search(s[i] + target);
if (j <= n) {
ans = Math.min(ans, j - i);
}
}
return ans === n + 1 ? 0 : ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| impl Solution {
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut res = n + 1;
let mut sum = 0;
let mut i = 0;
for j in 0..n {
sum += nums[j];
while sum >= target {
res = res.min(j - i + 1);
sum -= nums[i];
i += 1;
}
}
if res == n + 1 {
return 0;
}
res as i32
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int n = nums.Length;
long s = 0;
int ans = n + 1;
for (int i = 0, j = 0; i < n; ++i) {
s += nums[i];
while (s >= target) {
ans = Math.Min(ans, i - j + 1);
s -= nums[j++];
}
}
return ans == n + 1 ? 0 : ans;
}
}
|
Solution 2: Two Pointers#
We can use two pointers $j$ and $i$ to maintain a window, where the sum of all elements in the window is less than $target$. Initially, $j = 0$, and the answer $ans = n + 1$, where $n$ is the length of the array $nums$.
Next, the pointer $i$ starts to move to the right from $0$, moving one step each time. We add the element corresponding to the pointer $i$ to the window and update the sum of the elements in the window. If the sum of the elements in the window is greater than or equal to $target$, it means that the current subarray satisfies the condition, and we can update the answer, i.e., $ans = \min(ans, i - j + 1)$. Then we continuously remove the element $nums[j]$ from the window until the sum of the elements in the window is less than $target$, and then repeat the above process.
Finally, if $ans \leq n$, it means that there exists a subarray that satisfies the condition, return $ans$, otherwise return $0$.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
ans = n + 1
s = j = 0
for i, x in enumerate(nums):
s += x
while j < n and s >= target:
ans = min(ans, i - j + 1)
s -= nums[j]
j += 1
return ans if ans <= n else 0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
long s = 0;
int ans = n + 1;
for (int i = 0, j = 0; i < n; ++i) {
s += nums[i];
while (j < n && s >= target) {
ans = Math.min(ans, i - j + 1);
s -= nums[j++];
}
}
return ans <= n ? ans : 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
long long s = 0;
int ans = n + 1;
for (int i = 0, j = 0; i < n; ++i) {
s += nums[i];
while (j < n && s >= target) {
ans = min(ans, i - j + 1);
s -= nums[j++];
}
}
return ans == n + 1 ? 0 : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func minSubArrayLen(target int, nums []int) int {
n := len(nums)
s := 0
ans := n + 1
for i, j := 0, 0; i < n; i++ {
s += nums[i]
for s >= target {
ans = min(ans, i-j+1)
s -= nums[j]
j++
}
}
if ans == n+1 {
return 0
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
let s = 0;
let ans = n + 1;
for (let i = 0, j = 0; i < n; ++i) {
s += nums[i];
while (s >= target) {
ans = Math.min(ans, i - j + 1);
s -= nums[j++];
}
}
return ans === n + 1 ? 0 : ans;
}
|
