[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
26
209. 长度最小的子数组

给定一个含有$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
20
public 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\) 表示一个窗口:

  1. \(right\) 向右移增大窗口,直到窗口内的数字和大于等于了 \(target\);
  2. 记录此时的长度,\(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
23
public 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
26
public 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
38
public 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\)

  1. 如果 \(\ge target\),那么需要减少长度,继续判断所有长度为 \(len/4\) 的连续数字;
  2. 如果 \(< 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
39
public 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. 😉😃💗