标题：【leetcode】双指针算法技巧——滑动窗口
@水墨不写bug
正文开始：
滑动窗口介绍
滑动窗口是一种常用的算法技巧，用于解决一些涉及 连续子数组或子串 的问题。它的基本思想是 维护一个窗口，通过 在窗口内移动 来寻找满足特定条件的子数组或子串。
滑动窗口算法的步骤如下：
- 初始化窗口的起始位置left和终止位置right。
- 在每一步迭代中，将窗口右移一位，即将right加1，并根据题目要求更新窗口的状态。
- 如果窗口的状态满足题目给定的条件，那么根据题目要求处理结果。
- 如果窗口的状态不满足题目给定的条件，那么将窗口左移一位，即将left加1，继续迭代。
滑动窗口算法的时间复杂度通常为O(n)，其中n是数组或字符串的长度。它的优势在于可以将一些问题的时间复杂度从O(n^2)降低到O(n)。
四个必要步骤
滑动窗口的四个必要步骤：
（1）入窗口
（2）判断
（3）出窗口
（4）更新结果
对于前三条，它们的顺序一般相对彼此是固定的。更新结果的位置放在何处，需要根据题意判断。
（一）长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 连续子数组
[nums , nums + 1, ... , nums + r-1, nums + r]，并返回其长度。如果不存在符合条件的子数组，返回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 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
思路一：
找出所有的情况，遍历出所有sum==k的情况，分别求其长度，找出最小的长度即可。
以用例 1 具体来说：
[ 2 , 3 , 1 , 2 , 4 , 3 ]
创建left指针标记第一个元素，创建一个right指针向后遍历，同时将两指针之间的元素求和sum，如果sum==k，将此时的len存入数组ret，最终再找出ret中的最小值即可。
更优的算法从哪里来？是从暴力算法优化而来的！
思路二：
从宏观上我们先让sum尽可能的和k的值相近，这样才可能满足sum与k相等。假设我们此时确定了一个区间：
为了满足条件，
如果sum < k,继续增加sun的值；
如果sum==k，记录len（挑最小的记录）；
如果sum > k,则要减小sum的值；
现在就是确定如何加任何减的问题了。由于区间是连续的，不能有间断，所以从习惯上选择从左向右遍历，移动窗口。
这样我们就知道了，
left++，left指针向后移动实现减小sum（出窗口）
right++，right指针向后移动实现增加sum（入窗口）
参考代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(),len = INT_MAX,sum = 0;
/*将len初始化为很大的数，防止被求最小值的实际长度干扰*/
for(int left = 0,right = 0;right < n;++right)
{
//进窗口，sum维护
sum += nums[right];
while(sum >= target)//判断
{
len = min(len,right-left + 1);//更新结果
sum -= nums[left++];//出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};（二）无重复字符的最长字串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
让滑动窗口满足：窗口内所有元素都是不重复的。
做法：右端元素 ch 进⼊窗口的时候，哈希表统计这个字符的频次：
▪ 如果这个字符出现的频次超过 1 ，说明窗口内有重复元素，那么就从左侧开始划出窗口，
直到 ch 这个元素的频次变为 1 ，然后再更新结果。
▪ 如果没有超过 1 ，说明当前窗口没有重复元素，可以直接更新结果。
参考代码：
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int left = 0,right = 0,n = s.size(),ret = 0;
int hash[128] = {0};//使用数组模拟哈希表
while(right < n)
{
hash[s[right]]++;//进入窗口
//判断
while(hash[s[right]] > 1)
{
hash[s[left++]]--;//出窗口
}
ret = max(ret,right - left + 1);
right++;
}
return ret;
}
};（三）最大连续1的个数
给定一个二进制数组
nums和一个整数k，如果可以翻转最多k个0，则返回 数组中连续1的最大个数 。示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。提示：
1 <= nums.length <= 10^5nums[i]不是0就是10 <= k <= nums.length
不要自找麻烦，思路其实很简单；
要换个角度思考->
这道题的结果无非就是⼀段连续的 1 中间塞了 k 个 0 嘛。
我们可以把问题转化成：求数组中一段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。
参考代码：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int hash[2] = {0};
int n = nums.size(),ret = 0;
//if(k >= n) return n;
for(int right = 0,left = 0 ; right < n ; right++)
{
hash[ nums[right] ]++;//进窗口
while(hash[0] > k)//判断
{
hash[ nums[left++] ]--;//出窗口
}
ret = max(ret,right-left+1);
}
return ret;
}
};（四）将x减小到0的最小操作数
给你一个整数数组
nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将
x恰好 减到0，返回 最小操作数 ；否则，返回-1。示例 1：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。示例 2：
输入：nums = [5,6,7,8,9], x = 4 输出：-1示例 3：
输入：nums = [3,2,20,1,1,3], x = 10 输出：5 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^41 <= x <= 10^9
题目要求的是数组「左端+右端」两段连续的、和为 x 的最短数组；
换一个角度思考->
我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟
悉的「滑动窗口」问题了
本质和 （一）长度最小的子数组 是相同的代码结构，就一点不同——需要记录的数组长度从记录最小变成了记录最大。
参考代码：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum_all = 0,n = nums.size();
for(int i = 0;i < n;i++)
{
sum_all += nums[i];
}
int target = sum_all - x,sum = 0,left = 0,right = 0,ret = -1;
if(target == 0) return n;
for(;right < n;right++)
{
sum += nums[right];//进窗口
if(sum > target)//判断，right最佳位置
{
while(sum > target && (left < right))
{
sum -= nums[left++];//出窗口
}
}
if(sum == target)
{
ret = max(ret,right-left+1);
}
}
if(ret == -1) return ret;
else return n - ret;
}
};完~
未经作者同意禁止转载
