LeetCode 209 长度最小的子数组
🟡 中等
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
左程云 好理解。sum维护一个大于target 的小值，滑动左端点后再记录答案。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0;
int left = 0;
int res = INT_MAX;
for (int right = 0; right < nums.size(); right++) {
sum += nums[right];
//确保减掉之后还满足条件
while (sum - nums[left] >= target) {
//剪掉左边还能达标，就左移
sum -= nums[left];
left++;
}
if (sum >= target) {
res = min(res, right - left + 1);
}
}
return res==INT_MAX?0:res;
}
};
sum是维护一个小于target的值。当sum大于target时（也就是满足条件）就右移左端点。
while 不保证剪掉之后还满不满足条件，但是到最后停止的位置一定是不满足的，也就是sum小于target。
这里要先记录答案再右移。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum =0;
int right = nums.size()-1;
int ans = nums.size()+1;
//枚举起始位置,也可以枚举终止位置
for(int start = nums.size()-1;start>=0;start--){
sum+=nums[start];
//
while(sum>=target){
ans = min(ans,right-start+1);
sum-=nums[right];
right--;
}
}
return ans==nums.size()+1?0:ans;
}
};
枚举开始， 要从右边开始到左边。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum =0;
int right = nums.size()-1;
int ans = nums.size()+1;
for(int start = nums.size()-1;start>=0;start--){
sum+=nums[start];
while(sum>=target){
ans = min(ans,right-start+1);
sum-=nums[right];
right--;
}
}
return ans==nums.size()+1?0:ans;
}
};