「力扣」第 209 题:长度最小的子数组(中等)
中文网址:209. 长度最小的子数组 ;
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
方法一:暴力解法(超时)
- 暴力解法需要使用三层循环。
Java 代码:
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int minLen = len + 1;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += nums[k];
}
if (sum >= s) {
minLen = Math.min(minLen, j - i + 1);
}
}
}
if (minLen == len + 1){
return 0;
}
return minLen;
}
}
复杂度分析:
- 时间复杂度:$O(N^3)$,这里 $N$ 是数组的长度。
- 空间复杂度:$O(1)$。
方法二:构建前缀和数组(思路:空间换时间)
Java 代码:
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
// 由于 nums 全都是正整数,因此 preSum 严格单调增加
// preSum 表示 sum(nums[0..i))
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
int minLen = len + 1;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (preSum[j + 1] - preSum[i] >= s) {
minLen = Math.min(minLen, j - i + 1);
}
}
}
if (minLen == len + 1) {
return 0;
}
return minLen;
}
public static void main(String[] args) {
int s = 7;
int[] nums = {2, 3, 1, 2, 4, 3};
Solution2 solution2 = new Solution2();
int minSubArrayLen = solution2.minSubArrayLen(s, nums);
System.out.println(minSubArrayLen);
}
}
复杂度分析:
- 时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度。
- 空间复杂度:$O(1)$。
方法三:前缀和数组 + 二分法(思路:空间换时间)
充分利用题目给出的条件:正整数。
- 利用「数组是正整数」这个条件,构造前缀和数组,前缀和数组一定是严格增加的;
- 任意区间和可以通过前缀和数组得到,这是我们常见的一种做法。 起点固定的时候,区间越长,区间和越大。
Java 代码:构造前缀和数组,使用二分查找法,要考虑一些边界条件,编码易出错,了解即可
public class Solution {
// 构造前缀和数组,使用二分查找算法
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
// 由于 nums 全都是正整数,因此 preSum 严格单调增加
// preSum 表示 sum(nums[0..i))
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
// System.out.println(Arrays.toString(preSum));
int minLen = len + 1;
// 遍历一次,找到和大于等于 s 的最大下标
for (int i = 0; i < len; i++) {
// 对于前缀和数组来说,有 1 个位置的偏移,找使得区间和 sum[left..right] >= s 的最大的 left
int left = 0;
int right = i;
while (left < right) {
int mid = left + (right - left + 1) / 2;
// 什么时候解我们不需要呢,sum(nums[mid..i]) < s
if (preSum[i + 1] - preSum[mid] < s) {
// 下一轮搜索区间在 [left, mid - 1]
right = mid - 1;
} else {
left = mid;
}
}
// 这里后处理
// System.out.println("left = " + left);
// System.out.println("区间和 = " + (preSum[i + 1] - preSum[left]));
if (preSum[i + 1] - preSum[left] >= s) {
minLen = Math.min(minLen, i - left + 1);
}
}
if (minLen == len + 1) {
return 0;
}
return minLen;
}
public static void main(String[] args) {
int s = 15;
int[] nums = {1, 2, 3, 4, 5};
Solution3 solution3 = new Solution3();
int minSubArrayLen = solution3.minSubArrayLen(s, nums);
System.out.println(minSubArrayLen);
}
}
说明:虽然这个思路的解法时间复杂度和空间复杂度都不如「滑动窗口」,但我们也建议大家掌握。这是因为:
- 计算区间和,转向计算「前缀和」是常见的思路;
- 并且,根据输入「给定一个含有 n 个正整数」,前缀和一定单调增加,利用单调性确定一个下标,使用二分查找的思路也非常自然。
- 「二分查找」是很常见的算法思想,「前缀和」是很常见的算法技巧。我们都建议大家掌握。
复杂度分析:
- 时间复杂度:$O(N \log N)$,这里 $N$ 是数组的长度。
- 空间复杂度:$O(N)$。
方法四:滑动窗口
在做完了第 3 题、第 76 题以后,这道题就变得非常简单了,因为维护滑动窗口内的性质变得简单了。
情况 1 :当区间和小于
s
的时候,右区间的端点向右扩展,这一点依赖外层循环的遍历就可以完成;情况 2 :一旦区间和大于等于
s
,尝试一步一步缩小左区间端点,看看是否能得到一个更短的区间,满足区间和>=s
,这一步通过一个内层循环实现。
Java 代码:
public class Solution {
// 向右边扩散得到和越来越大
// 向左边界扩散得到和越来越小
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
int left = 0;
int right = 0;
int sum = 0;
// 保持性质:[left, right) >= s
int minLen = len + 1;
while (right < len) {
sum += nums[right];
right++;
while (sum >= s) {
minLen = Math.min(minLen, right - left);
sum -= nums[left];
left++;
}
}
if (minLen == len + 1) {
return 0;
}
return minLen;
}
}
Python 代码:在理解的基础上,记住下面这个写法,右指针也是用于遍历的指针
from typing import List
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
size = len(nums)
# 特判
if size == 0:
return 0
left = 0
right = 0
# 区间和
interval_sum = 0
min_len = size + 1
while right < size:
interval_sum += nums[right]
right += 1
while interval_sum >= s:
min_len = min(min_len, right - left)
interval_sum -= nums[left]
left += 1
if min_len == size + 1:
return 0
return min_len
if __name__ == '__main__':
s = 7
nums = [2, 3, 1, 2, 4, 3]
solution = Solution()
result = solution.minSubArrayLen(s, nums)
print(result)
复杂度分析:
- 时间复杂度:$O(N)$,这里 $N$ 是数组的长度。
- 空间复杂度:$O(1)$。
(本节完)