题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
进阶：
- 如果你已经实现
O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
解法
方法一：前缀和 + 二分查找
我们先预处理出数组 $nums$ 的前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 前 $i$ 项元素之和。由于数组 $nums$ 中的元素都是正整数，因此数组 $s$ 也是单调递增的。另外，我们初始化答案 $ans = n + 1$，其中 $n$ 为数组 $nums$ 的长度。
接下来，我们遍历前缀和数组 $s$，对于其中的每个元素 $s[i]$，我们可以通过二分查找的方法找到满足 $s[j] \geq s[i] + target$ 的最小下标 $j$，如果 $j \leq n$，则说明存在满足条件的子数组，我们可以更新答案，即 $ans = min(ans, j - i)$。
最后，如果 $ans \leq n$，则说明存在满足条件的子数组，返回 $ans$，否则返回 $0$。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
| 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;
}
}
|
方法二：双指针
我们注意到，数组 $\textit{nums}$ 中的元素均为正整数，我们可以考虑使用双指针来维护一个滑动窗口。
具体地，我们定义两个指针 $\textit{l}$ 和 $\textit{r}$ 分别表示滑动窗口的左边界和右边界，用一个变量 $\textit{s}$ 代表滑动窗口中的元素和。
在每一步操作中，我们移动右指针 $\textit{r}$，使得滑动窗口中加入一个元素，如果此时 $\textit{s} \ge \textit{target}$，我们就更新最小长度 $\textit{ans} = \min(\textit{ans}, \textit{r} - \textit{l} + 1$，并将左指针 $\textit{l}$ 循环向右移动，直至有 $\textit{s} < \textit{target}$。
最后，如果最小长度 $\textit{ans}$ 仍为初始值，我们就返回 $0$，否则返回 $\textit{ans}$。
时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。
| 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
|
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 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;
}
}
|
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 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | 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;
}
|