用滑动窗口来记录序列, 每当滑动窗口中的 sum 超过 s, 就去更新最小值,并根据先进先出的原则更新滑动窗口,直至 sum 刚好小于 s
这道题目和 leetcode 3 号题目有点像,都可以用滑动窗口的思路来解决
关键点
滑动窗口简化操作(滑窗口适合用于求解这种要求连续的题目)
代码
语言支持:JS,C++,Python
Python Code:
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
l = total = 0
ans = len(nums) + 1
for r in range(len(nums)):
total += nums[r]
while total >= s:
ans = min(ans, r - l + 1)
total -= nums[l]
l += 1
return 0 if ans == len(nums) + 1 else ans
JavaScript Code:
/*
* @lc app=leetcode id=209 lang=javascript
*
* [209] Minimum Size Subarray Sum
*
*/
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (s, nums) {
if (nums.length === 0) return 0;
const slideWindow = [];
let acc = 0;
let min = null;
for (let i = 0; i < nums.length + 1; i++) {
const num = nums[i];
while (acc >= s) {
if (min === null || slideWindow.length < min) {
min = slideWindow.length;
}
acc = acc - slideWindow.shift();
}
slideWindow.push(num);
acc = slideWindow.reduce((a, b) => a + b, 0);
}
return min || 0;
};
C++ Code:
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int num_len= nums.size();
int left=0, right=0, total=0, min_len= num_len+1;
while (right < num_len) {
do {
total += nums[right++];
} while (right < num_len && total < s);
while (left < right && total - nums[left] >= s) total -= nums[left++];
if (total >=s && min_len > right - left)
min_len = right- left;
}
return min_len <= num_len ? min_len: 0;
}
};
复杂度分析
时间复杂度:$O(N)$,其中 N 为数组大小。
空间复杂度:$O(1)$
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解
扩展
如果题目要求是 sum = s, 而不是 sum >= s 呢?
eg:
var minSubArrayLen = function (s, nums) {
if (nums.length === 0) return 0;
const slideWindow = [];
let acc = 0;
let min = null;
for (let i = 0; i < nums.length + 1; i++) {
const num = nums[i];
while (acc > s) {
acc = acc - slideWindow.shift();
}
if (acc === s) {
if (min === null || slideWindow.length < min) {
min = slideWindow.length;
}
slideWindow.shift();
}
slideWindow.push(num);
acc = slideWindow.reduce((a, b) => a + b, 0);
}
return min || 0;
};