[Leetcode][209. 长度最小的子数组] 5种方法：暴力，双指针，前缀和，前缀和 + 二分查找，二分查找
By Long Luo
Leetcode 209. 长度最小的子数组 题目如下：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
26209. 长度最小的子数组
给定一个含有$n$个正整数的数组和一个正整数$\textit{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 <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
进阶：
如果你已经实现 $O(n)$ 时间复杂度的解法, 请尝试设计一个 $O(n\log n)$ 时间复杂度的解法。
方法一：暴力法
思路与算法：
很容易想到，使用 \(2\) 个循环，枚举 \(\textit{nums}\) 中的每个下标作为子数组的开始下标，对于每个子数组 \(i\)，满足 \(i \le x \le j\)，使得：
\[ sum=\sum_{x=i}^{j}\textit{nums}[x] \ge $\textit{target} \]
，并更新子数组的最小长度 \(j-i+1\)。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int minSubArrayLen_bf(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int ans = Integer.MAX_VALUE;
for (int i = 0; i < len; i++) {
int sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
if (sum >= target) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
复杂度分析：
时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
空间复杂度：\(O(1)\)。
方法二：双指针 + 滑动窗口
思路与算法：
因为求连续子数组的和大于某个值，那么很容易想到使用滑动窗口，使用双指针 \(left\) 和 \(right\) 表示一个窗口：
- \(right\) 向右移增大窗口，直到窗口内的数字和大于等于了 \(target\);
- 记录此时的长度，\(left\) 向右移动，开始减少长度，每减少一次，就更新最小长度，直到当前窗口内的数字和 \(< target\)，回到第 \(1\) 步。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public int minSubArrayLen_sw(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int ans = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
int right = 0;
while (right < len) {
sum += nums[right];
while (sum >= target) {
ans = Math.min(ans, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
复杂度分析：
时间复杂度：\(O(N)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度，指针 \(\textit{start}\) 和 \(\textit{end}\) 最多各移动 \(n\) 次。
空间复杂度：\(O(1)\)。