C++算法——双指针、滑动窗口类_c++滑窗类

一.滑动窗口

滑动窗口一个比较重要的问题是:
（1）循环退出条件
（2）前后两个指针的快慢
（3）结构：双循环？
伪代码：
while(){//用for也行
sum+=**

while(sum<=k)
{
//判断是否计数
(ans<)?ans+1:ans;
sum-=**;
start++;
}
end++;
}

1.剑指 Offer II 008. 和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//滑动窗口
//关键在于窗口的滑动模式 右慢1 左快n
class Solution {
public:
        int minSubArrayLen(int target, vector<int>& nums){

        int length = nums.size();
        int ans = INT_MAX ;
        int start = 0, end = 0, sum = 0;
        while (end < length)
        {
            sum += nums[end];

            while (sum >= target)
            {
                ans=(end-start+1)<ans?(end-start+1):ans;
                sum -= nums[start];
                start++;
            }
            end++;
        }

        if (ans == INT_MAX )//没找到大于target的子数组
            ans = 0;

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28