LeetCode 209. 长度最小的子数组（最长子数组长度）

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶：

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

这道题目和 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

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

= 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

= s) { if (min === null || slideWindow.length

a + b, 0); } return min || 0;};

C++ Code：

class Solution {public: int minSubArrayLen(int s, vector

& nums) { int num_len= nums.size; int left=0, right=0, total=0, min_len= num_len+1; while (right

= s) total -= nums[left++]; if (total >=s && min_len > right - left) min_len = right- left; } return min_len

=s && min_len > right - left) min_len = right- left; } return min_len

right - left) min_len = right- left; } return min_len

复杂度分析

时间复杂度：$O(N)$，其中 N 为数组大小。

空间复杂度：$O(1)$

如果题目要求是 sum = s, 而不是 sum >= s 呢？

= s 呢？

var minSubArrayLen = function (s, nums) { if (nums.length === 0) return 0; const slideWindow = ; let acc = 0; let min = null; for (let i = 0; i

s) { acc = acc - slideWindow.shift; } if (acc === s) { if (min === null || slideWindow.length

a + b, 0); } return min || 0;};