0209. 长度最小的子数组 · ttttt

# 0209. 长度最小的子数组 ## 题目地址(209. 长度最小的子数组) <https://leetcode-cn.com/problems/minimum-size-subarray-sum/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。示例：输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。进阶：如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 ``` ``` ## 前置知识 - 滑动窗口 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路用滑动窗口来记录序列，每当滑动窗口中的 sum 超过 s，就去更新最小值，并根据先进先出的原则更新滑动窗口，直至 sum 刚好小于 s ![](https://img.kancloud.cn/9b/73/9b738d61208b2c1b9ed9a160968f03fc_826x753.jpg) > 这道题目和 leetcode 3 号题目有点像，都可以用滑动窗口的思路来解决 ## 关键点 - 滑动窗口简化操作(滑窗口适合用于求解这种要求`连续`的题目) ## 代码 - 语言支持：JS，C++，Python Python Code： ``` <pre class="calibre18">``` 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： ``` <pre class="calibre18">``` /* * @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： ``` <pre class="calibre18">``` 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)O(N)O(N)，其中 N 为数组大小。 - 空间复杂度：O(1)O(1)O(1) 欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg) ## 扩展如果题目要求是 sum = s, 而不是 sum >= s 呢？ eg: ``` <pre class="calibre18">``` 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; }; ``` ``` 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)