【Leetcode算法题】209. 长度最小的子数组

By Long Luo

209. 长度最小的子数组题目如下:

  1. 长度最小的子数组

给定一个含有nn个正整数的数组和一个正整数target\textit{target}

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回00

示例 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)时间复杂度的解法, 请尝试设计一个O(nlog(n))O(n log(n))时间复杂度的解法。

方法一:暴力

思路与算法:

最直观的方法,设置2个循环。初始化子数组的最小长度为无穷大,枚举数组nums\text{nums}中的每个下标作为子数组的开始下标,对于每个开始下标ii,对于满足iji \le j,使得从nums[i]\text{nums}[i]nums[j]\text{nums}[j]的元素和大于或等于target\textit{target},并更新子数组的最小长度ji+1j-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
public int minSubArrayLen(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 = nums[i];
if (sum >= target) {
return 1;
}

for (int j = i + 1; 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(N2)O(N^2),其中NN是数组nums\textit{nums}的长度。
  • 空间复杂度:O(N)O(N)

方法二:滑动窗口

思路与算法:

可以使用滑动窗口的方法降低时间复杂度。

定义两个指针start\textit{start}end\textit{end}分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量sum\textit{sum}存储子数组中的元素和(即从nums[start]\text{nums}[\textit{start}]nums[end]\text{nums}[\textit{end}]的元素和)。

初始状态下,start\textit{start}end\textit{end}都指向下标00sum\textit{sum}的值为00

每一轮迭代,将nums[end]\text{nums}[end]加到sum\textit{sum},如果sumtarget\textit{sum} \ge \textit{target},则更新子数组的最小长度(此时子数组的长度是endstart+1\textit{end}-\textit{start}+1),然后将 nums[start]\text{nums}[start]sum\textit{sum}中减去并将start\textit{start}右移,直到sum<target\textit{sum} < \textit{target},在此过程中同样更新子数组的最小长度。在每一轮迭代的最后,将end\textit{end}右移。

代码如下所示:

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(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;
int ans = Integer.MAX_VALUE;
int start = 0;
int end = 0;
int sum = 0;
while (end < len) {
sum += nums[end];
while (sum >= target) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}

end++;
}

return ans == Integer.MAX_VALUE ? 0 : ans;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度,指针start\textit{start}end\textit{end}最多各移动nn次。
  • 空间复杂度:O(N)O(N)

方法三:前缀和 + 滑动窗口

思路与算法:

对于求连续数组之和的问题,首先想到的是前缀和。我们创建一个数组sums\text{sums}用于存储数组nums\text{nums}的前缀和,其中sums[i]\text{sums}[i]表示从nums[0]\text{nums}[0]nums[i1]\text{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 (left < right && right <= len) {
int sum = prefixSums[right] - prefixSums[left];
if (sum >= target) {
ans = Math.min(ans, right - left);
left++;
} else if (sum < target) {
right++;
}
}

return ans == Integer.MAX_VALUE ? 0 : ans;
}

复杂度分析:

  • 时间复杂度:O(N2)O(N^2),其中NN是数组nums\textit{nums}的长度。
  • 空间复杂度:O(N)O(N)

方法四:前缀和 + 二分查找

思路与算法:

在方法三的基础上,找到长度最小的子数组需要O(n)O(n)的时间。如果使用二分查找,则可以将时间优化到O(logn)O(\log n)

因为数组中每个元素都为正,所以前缀和一定是递增的,这一点保证了二分的正确性。

为了使用二分查找,需要额外创建一个前缀和数组prefixSums\text{prefixSums},其中prefixSums[i]\text{prefixSums}[i]表示从nums[0]\text{nums}[0]nums[i1]\text{nums}[i-1]的元素和。得到前缀和之后,对于每个开始下标ii,可通过二分查找得到大于或等于ii的最小下标bound\textit{bound},使得sums[bound]sums[i1]target\text{sums}[\textit{bound}]-\text{sums}[i-1] \ge \text{target},并更新子数组的最小长度bound(i1)\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
39
40
41
42
43
44
45
46
47
48
public int minSubArrayLen_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 value = target + prefixSums[i - 1];
int upperBound = binarySearch(prefixSums, i, value);
if (upperBound == -1) {
continue;
}
if (upperBound <= len) {
ans = Math.min(ans, upperBound - i + 1);
}
}

return ans == Integer.MAX_VALUE ? 0 : ans;
}

public int binarySearch(int[] nums, int start, int target) {
int len = nums.length;
if (start > len || nums[len - 1] < target) {
return -1;
}

if (nums[start] > target) {
return start;
}

int end = len - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid;
} else if (nums[mid] < target) {
start = mid + 1;
}
}

return end;
}

复杂度分析:

  • 时间复杂度:O(nlogn)O(n \log n),其中nn是数组的长度。需要遍历每个下标作为子数组的开始下标,遍历的时间复杂度是O(n)O(n),对于每个开始下标,需要通过二分查找得到长度最小的子数组,二分查找得时间复杂度是O(logn)O(\log n),因此总时间复杂度是O(nlogn)O(n \log n)

  • 空间复杂度:O(n)O(n),其中nn是数组的长度。额外创建数组sums\text{sums}存储前缀和。

小结

从代码运行来看,方法三是最快的。