Leetcode-滑动窗口
1 .给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 \[numsl, numsl+1, …, numsr-1, numsr\] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
最小的 连续子数组 : eg , \[1,2,3,4,4\] 连续数组 \[1,2\] \[2,3,4\]; 但是 \[1,4,4\] ， 下标连续
还是需要双指针，构成滑动窗口，用这窗口遍历全部数据 ，窗口结合条件是可变的，窗口大小则是我们呢的答案
滑动窗口： 窗口起点终点，和控制窗口大小的条件（本题约束窗口大小的条件是 窗口内的值总和应大于target，如果小往右扩大窗口，大了左边缩小窗口）
int minSubArrayLen(int target, vector<int> &nums) {
int left = 0;
int right = 0;
int len = nums.size();
if (nums.size() == 1) {
return nums[0] == target ? 1 : 0;
}
int sum = 0;
int ret = len;
while (right < len) {
sum = sum + nums[right];
while (sum >= target) { //窗口内的总和符合条件，则左边收缩
ret = min(ret, right - left + 1);
sum = sum - nums[left];
left++;
}
right++;
}
return ret==INT_MAX?0:ret;
}
2 . 摘水果问题 （其实套了一层皮： 窗口内只能存在两种数字，窗口最大值）
int totalFruit(vector<int> &tree) {
int res = 0;
// 水果编号到数量的映射
unordered_map<int, int> veg2cnt;
int n = tree.size();
// 窗口左边界
int l = 0;
// 窗口右边界
for (int i = 0; i < n; ++i) {
++veg2cnt[tree[i]];
// 一旦发现超过大小，则不断收缩窗口
while (veg2cnt.size() > 2) {
int currTree = tree[l];
--veg2cnt[currTree];
if (veg2cnt[currTree] == 0) {
veg2cnt.erase(currTree);
}
++l;
}
// 记录最大的窗口大小
res = max(res, i - l + 1);
}
return res;
}