題目描述
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s 垃喊，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0绢涡。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組。
進(jìn)階:
如果你已經(jīng)完成了O(n) 時(shí)間復(fù)雜度的解法, 請嘗試 O(n log n) 時(shí)間復(fù)雜度的解法遣疯。
分析
使用滑動窗口的算法
要求是連續(xù)子數(shù)組雄可，所以我們必須定義 i，j兩個(gè)指針缠犀，i 向前遍歷数苫，j 向后遍歷，相當(dāng)與一個(gè)滑塊辨液，這樣所有的子數(shù)組都會在 [i...j] 中出現(xiàn)虐急，如果 nums[i..j] 的和小于目標(biāo)值 s，那么j向后移一位滔迈，再次比較止吁，直到大于目標(biāo)值 s 之后被辑，i 向前移動一位，縮小數(shù)組的長度赏殃。遍歷到i到數(shù)組的最末端敷待，就算結(jié)束了，如果不存在符合條件的就返回 0仁热。
代碼
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
if(nums.size() < 1) {
return 0;
}
int len = 0;
int begin = 0;
int sum = 0;
int end = -1;
while(begin < nums.size()){
if(end + 1 < nums.size() && sum < s) {
sum += nums[++end];
} else {
sum -= nums[begin++];
}
if(sum >= s) {
int l = end - begin + 1;
len = len == 0 || l < len ? l : len;
}
}
return len;
}
};
題目鏈接
https://leetcode-cn.com/problems/minimum-size-subarray-sum/description/
