【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数
1. 长度最小的子数组 - 力扣（LeetCode）
1.题目解析：
2.算法原理
（1）方法一：暴力列举出所有的子数组的和
时间复杂度：O（n**2）：枚举所有子数组O（n**2）
（2）方法二：
利用单调性（两个指针都不回退），使用"同向双指针"（其实就是滑动窗口）来优化
那么滑动窗口过程是怎么样的？
<1>left = 0，rght = 0
<2>进窗口
<3>判断 并决定什么时候出窗口
(其中二三步是循环的）
还有一步更新结果：这一步可能在<2>，也可能在<3>
以【2，3，1，2，4，3】为例模拟这个过程
开始left和right都指向2（第一个元素），
然后开始进窗口（right++），right指向3，sum从0变为2，
然后进行判断，如果sum>target，更新结果并出窗口（也就是left++）；如果sum<=target，继续进窗口（也就是right++)
正确性验证：
利用单调性，规避了很多没有必要的枚举行为(也就是当 sum>target时，right不用继续++）
时间复杂度：O（N）
最坏情况：left和right都走到数组的最后，也就是N+N=2N
3.代码实现
class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int ret = Integer.MAX_VALUE;for(int left=0,right=0;right<nums.length;right++) {sum+=nums[right];//进窗口while(sum>=target) {//判断ret = Math.min(right-left+1,ret);//更新结果sum-=nums[left];left++;}}//要考虑特殊情况：不存在return ret==Integer.MAX_VALUE ? 0:ret;}
}2. 无重复字符的最长子串 - 力扣（LeetCode）
1.题目解析：
2.算法原理
方法一：暴力枚举 + 哈希表（判断字符是否重复出现）
时间复杂度：O（N**2）
方法二：利用规律，使用滑动窗口来解决问题
<1>left = 0，rght = 0
<2>进窗口（right++）—>让字符进入哈希表
<3>判断（窗口内是否出现重复字符）
有重复字符就出窗口（left++），从哈希表中删除该字符，这个过程需要一直重复，直到left找到重复的字符
<4>更新结果：在出完窗口到没有重复字符后就统计结果
3.代码实现
class Solution {public int lengthOfLongestSubstring(String s) {char[] ss = s.toCharArray();//字符串转为字符数组int[] hash = new int[128]; //用数组模拟哈希表int len = 0;for(int left=0,right=0;right<s.length();right++) {//进窗口hash[ss[right]]++;while(hash[ss[right]]>1) {//有重复字符//删除hash[ss[left]]--;//出窗口left++;}//更新结果len = Math.max(len,right-left+1);}return len;}
}3. 最大连续1的个数 III - 力扣（LeetCode）
1.题目解析：
2.算法原理：
问题转化：找出最长的子数组，0的个数不超过k个
方法一：暴力枚举+zero计数器
方法二：在暴力的情况下不让right回退—>滑动窗口
<1>left = 0，rght = 0
<2>进窗口:right++，如果是1，无视；如果是0，计数器+1
<3>判断(zero>k) 并决定什么时候出窗口(left++，计数器-1）
<4>更新结果：出窗口结束
3.代码实现：
class Solution {public int longestOnes(int[] nums, int k) {int count=0;int zero=0;for(int left=0,right=0;right<nums.length;right++) {//进窗口if(nums[right]==0){zero++;}while(zero>k) {//判断：0的个数超过k个//出窗口if(nums[left]==0) {zero--;}left++;}count=Math.max(count,right-left+1);}return count;}
}1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
1.题目解析：
2.算法原理：
正难则反：找出最长的子数组的长度（len），所有元素的和正好等于sum-x（target），那么最后求的就是n-len的最小值
<1>left = 0，rght = 0
<2>进窗口—>Sum+=nums[right]
<3>判断 Sum>target(此处不应该有==，因为要等于不能出窗口）
并决定什么时候出窗口—>sum-=nums[left]
<4>更新结果：这个时候需要加上判断sum==target
3.代码实现：
class Solution {public int minOperations(int[] nums, int x) {int Sum=0;for(int a:nums) Sum+=a;int sum=0;int target = Sum-x;//处理细节if(target<0) {return -1;}int ret=-1;for(int left=0,right=0;right<nums.length;right++) {//进窗口sum+=nums[right];//判断while(sum>target) {//出窗口sum-=nums[left++];}//更新结果if(sum==target) {ret=Math.max(right-left+1,ret);}}return (ret==-1)?(-1):(nums.length-ret);}
}