[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)\)。
方法三：前缀和 + 滑动窗口
思路与算法：
对于求连续数组之和的问题，还可以使用前缀和来求解。
我们创建一个数组 \(\textit{prefixSums}\) 用于存储数组 \(\textit{nums}\) 的前缀和，其中 \(\textit{prefixSums}[i]\) 表示从 \(\textit{nums}[0]\) 到 \(\textit{nums}[i-1]\) 的元素和。
得到前缀和之后，我们可以使用滑动窗口来计算最小的窗口长度。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
26public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int ans = Integer.MAX_VALUE;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; i++) {
prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
}
int left = 0;
int right = 1;
while (right <= len) {
int sum = prefixSums[right] - prefixSums[left];
if (sum >= target) {
ans = Math.min(ans, right - left);
left++;
} else {
right++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
复杂度分析：
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(N)\)。
方法四：前缀和 + 二分查找
思路与算法：
在方法三的基础上，找到长度最小的子数组需要 \(O(n)\) 的时间，因为数组中元素都 \(>0\)，所以前缀和中元素值都是递增的，那么可以使用二分查找，将时间优化到 \(O(logn)\)。
得到前缀和之后，对于每个开始下标 \(i\)，可通过二分查找得到 \(\ge i\) 的最小下标 \(\textit{bound}\)，使得 \(\textit{prefixSums}[\textit{bound}]-\textit{prefixSums}[i-1] \ge \text{target}\)，并更新子数组的最小长度 \(\textit{bound} - (i-1)\)。
代码如下所示：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
38public int minSubArrayLen_prefix_bs(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int ans = Integer.MAX_VALUE;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; i++) {
prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= len; i++) {
int upperBound = binarySearch(prefixSums, i, len, target + prefixSums[i - 1]);
if (upperBound != -1) {
ans = Math.min(ans, upperBound - i + 1);
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
public int binarySearch(int[] nums, int left, int right, int target) {
if (nums[right] < target) {
return -1;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return nums[left] >= target ? left : -1;
}
复杂度分析：
时间复杂度：\(O(N \log N)\)，其中 \(N\) 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 \(O(N)\)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 \(O(\log N)\)，因此总时间复杂度是 \(O(N \log N)\)。
空间复杂度：\(O(N)\)，需要额外创建数组 \(\textit{prefixSums}\) 存储前缀和。
方法五：二分查找
思路与算法：
方法四中二分查找的关键在于 \(\textit{prefixSums}\) 数组的定义，这里提供另外一种二分查找的思路。
因为数组中元素都 \(>0\)，而寻找连续的数字和大于等于 \(\textit{target}\) 的最小长度，要寻找的 \(\textit{minLen}\) 的范围在 \(0\) 到 \(len\) 之间。
但如何进行二分呢？
长度为 \(1\) 的所有连续数字中最大的和、长度为 \(2\) 的所有连续数字中最大的和、长度为 \(3\) 的所有连续数字中最大的和、…、长度为 \(len\) 的所有连续数字中最大的和，同样是一个升序数组。
算法的话就是对长度进行二分，寻求满足条件的最小长度。
对于长度为 \(len\) 的数组，我们先去判断长度为 \(len/2\) 的连续数字中最大的和是否大于等于 \(target\)。
- 如果 \(\ge target\)，那么需要减少长度，继续判断所有长度为 \(len/4\) 的连续数字；
- 如果 \(< target\)，需要增加长度，我们继续判断所有长度为 \((len/2+len)/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
39public static int minSubArrayLen_bs(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int left = 0;
int right = len;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxSum = getMaxSum(nums, mid);
if (mid == len && maxSum < target) {
return 0;
}
if (maxSum >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left <= len ? left : 0;
}
public static int getMaxSum(int[] nums, int segLen) {
int sum = 0;
for (int i = 0; i < segLen; i++) {
sum += nums[i];
}
int ans = sum;
for (int i = segLen; i < nums.length; i++) {
sum += nums[i];
sum -= nums[i - segLen];
ans = Math.max(ans, sum);
}
return ans;
}
复杂度分析：
- 时间复杂度：\(O(N \log N)\)，其中 \(N\) 是数组的长度。
- 空间复杂度：\(O(1)\)。
小结
从代码实际运行情况来看，方法三是最快的。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗