滑动窗口(双指针的又一应用)

发布时间 2024-01-11 12:18:17作者: 云撤~

滑动窗口相当于双指针的变形,通过j指向末尾边界,这样遍历就只有O(n)的数量级,再通过i指针作为起始边界,while循环确定最短的长度。因为i j所框定的边界像窗口,所以叫滑动窗口。
用于解决的问题是最优区间的问题,记忆方法是右遍历,左判断,确定最佳区间。
还有一个技巧是可以用INT_MAX表示一个很大的数。

点击查看代码
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();int nummin=INT32_MAX;
int i=0;int sum=0;
for(int j=0;j<n;j++){
sum+=nums[j];
while(sum>=target){
   nummin= min(nummin,j-i+1);
sum-=nums[i];
i++;
}
}
if(nummin==INT32_MAX){
return 0;
}
else{return nummin;}
    }
};