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] ≥ s[i] + target by binary search. If j ≤ 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 ≤ n, it means that there exists a subarray that satisfies the condition, return ans, otherwise return 0.
The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRustC#
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
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;
}
}(code-box)
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 ≤ 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.
PythonJavaC++GoTypeScript
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l = s = 0
ans = inf
for r, x in enumerate(nums):
s += x
while s >= target:
ans = min(ans, r - l + 1)
s -= nums[l]
l += 1
return 0 if ans == inf else ans(code-box)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int l = 0, n = nums.length;
long s = 0;
int ans = n + 1;
for (int r = 0; r < n; ++r) {
s += nums[r];
while (s >= target) {
ans = Math.min(ans, r - l + 1);
s -= nums[l++];
}
}
return ans > n ? 0 : ans;
}
}(code-box)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, n = nums.size();
long long s = 0;
int ans = n + 1;
for (int r = 0; r < n; ++r) {
s += nums[r];
while (s >= target) {
ans = min(ans, r - l + 1);
s -= nums[l++];
}
}
return ans > n ? 0 : ans;
}
};(code-box)
func minSubArrayLen(target int, nums []int) int {
l, n := 0, len(nums)
s, ans := 0, n+1
for r, x := range nums {
s += x
for s >= target {
ans = min(ans, r-l+1)
s -= nums[l]
l++
}
}
if ans > n {
return 0
}
return ans
}(code-box)
function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
let [s, ans] = [0, n + 1];
for (let l = 0, r = 0; r < n; ++r) {
s += nums[r];
while (s >= target) {
ans = Math.min(ans, r - l + 1);
s -= nums[l++];
}
}
return ans > n ? 0 : ans;
}(code-box)
