第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0209. 长度最小的子数组

题目地址(209. 长度最小的子数组)

题目描述

1
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
2
3
4
5
示例:
6
7
输入:s = 7, nums = [2,3,1,2,4,3]
8
输出:2
9
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
10
11
12
进阶:
13
14
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

用滑动窗口来记录序列, 每当滑动窗口中的 sum 超过 s, 就去更新最小值,并根据先进先出的原则更新滑动窗口,直至 sum 刚好小于 s
209.minimum-size-subarray-sum
这道题目和 leetcode 3 号题目有点像,都可以用滑动窗口的思路来解决

关键点

  • 滑动窗口简化操作(滑窗口适合用于求解这种要求连续的题目)

代码

  • 语言支持:JS,C++,Python
Python Code:
1
class Solution:
2
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
3
l = total = 0
4
ans = len(nums) + 1
5
for r in range(len(nums)):
6
total += nums[r]
7
while total >= s:
8
ans = min(ans, r - l + 1)
9
total -= nums[l]
10
l += 1
11
return 0 if ans == len(nums) + 1 else ans
Copied!
JavaScript Code:
1
/*
2
* @lc app=leetcode id=209 lang=javascript
3
*
4
* [209] Minimum Size Subarray Sum
5
*
6
*/
7
/**
8
* @param {number} s
9
* @param {number[]} nums
10
* @return {number}
11
*/
12
var minSubArrayLen = function (s, nums) {
13
if (nums.length === 0) return 0;
14
const slideWindow = [];
15
let acc = 0;
16
let min = null;
17
18
for (let i = 0; i < nums.length + 1; i++) {
19
const num = nums[i];
20
21
while (acc >= s) {
22
if (min === null || slideWindow.length < min) {
23
min = slideWindow.length;
24
}
25
acc = acc - slideWindow.shift();
26
}
27
28
slideWindow.push(num);
29
30
acc = slideWindow.reduce((a, b) => a + b, 0);
31
}
32
33
return min || 0;
34
};
Copied!
C++ Code:
1
class Solution {
2
public:
3
int minSubArrayLen(int s, vector<int>& nums) {
4
int num_len= nums.size();
5
int left=0, right=0, total=0, min_len= num_len+1;
6
while (right < num_len) {
7
do {
8
total += nums[right++];
9
} while (right < num_len && total < s);
10
while (left < right && total - nums[left] >= s) total -= nums[left++];
11
if (total >=s && min_len > right - left)
12
min_len = right- left;
13
}
14
return min_len <= num_len ? min_len: 0;
15
}
16
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为数组大小。
  • 空间复杂度:$O(1)$
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解

扩展

如果题目要求是 sum = s, 而不是 sum >= s 呢?
eg:
1
var minSubArrayLen = function (s, nums) {
2
if (nums.length === 0) return 0;
3
const slideWindow = [];
4
let acc = 0;
5
let min = null;
6
7
for (let i = 0; i < nums.length + 1; i++) {
8
const num = nums[i];
9
10
while (acc > s) {
11
acc = acc - slideWindow.shift();
12
}
13
if (acc === s) {
14
if (min === null || slideWindow.length < min) {
15
min = slideWindow.length;
16
}
17
slideWindow.shift();
18
}
19
20
slideWindow.push(num);
21
22
acc = slideWindow.reduce((a, b) => a + b, 0);
23
}
24
25
return min || 0;
26
};
Copied!
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。