1. 題目

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。
如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

示例: 輸入: s = 7, nums = [2,3,1,2,4,3] 輸出: 2 解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 滑動窗口解題

• 貪心思想
• 總和大了，sum減去左邊界，左端邊界+1
• 總和小了，右邊界+1，sum加上右邊界

class Solution { //C++ public:int minSubArrayLen(int s, vector<int>& nums) {if(nums.size() == 0)return 0;int i = 0, j = 0, len = INT_MAX, sum = nums[0];while(j < nums.size()){if(sum < s){j++;if(j < nums.size())sum += nums[j];}else if(sum >= s){if(j-i+1 < len)len = j-i+1;sum -= nums[i];i++;}}if(len == INT_MAX)return 0;return len;} };

class Solution:# py3def minSubArrayLen(self, s: int, nums: List[int]) -> int:minlen = float('inf')l, r, ans = 0, 0, 0for r in range(len(nums)):ans += nums[r]while ans >= s:minlen = min(minlen, r-l+1)ans -= nums[l]l += 1return minlen if minlen!=float('inf') else 0

48 ms 15.3 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 209. 长度最小的子数组（滑动窗口）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。