209.minimum-size-subarray-sum.md

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

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

题目描述

给定一个含有 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

这道题目和 leetcode 3 号题目有点像，都可以用滑动窗口的思路来解决

关键点

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

代码

• 语言支持：JS，C++，Python

Python Code：

classSolution: defminSubArrayLen(self, s: int, nums: List[int]) ->int: l=total=0ans=len(nums) +1forrinrange(len(nums)): total+=nums[r] whiletotal>=s: ans=min(ans, r-l+1) total-=nums[l] l+=1return0ifans==len(nums) +1elseans

JavaScript Code：

/* * @lc app=leetcode id=209 lang=javascript * * [209] Minimum Size Subarray Sum * *//** * @param {number} s * @param {number[]} nums * @return {number} */varminSubArrayLen=function(s,nums){if(nums.length===0)return0;constslideWindow=[];letacc=0;letmin=null;for(leti=0;i<nums.length+1;i++){constnum=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);}returnmin||0;};

C++ Code：

classSolution { public:intminSubArrayLen(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:

varminSubArrayLen=function(s,nums){if(nums.length===0)return0;constslideWindow=[];letacc=0;letmin=null;for(leti=0;i<nums.length+1;i++){constnum=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);}returnmin||0;};

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。