滑动窗口系列(不定长滑动窗口长度) 9/1
1.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路:
不定长的滑动窗口长度，其中windowSize=无重复字符的最长字串的长度；
那么如何得到最长字串的长度？
使用哈希表+while循环遍历
如果遍历到的字母在哈希表中存在,此时字串中出现重复字符;
此时我们就要移动left改变滑动窗口的左边界；使得哈希表中不再出现s.charAt(right);
因为新的字符串的开始一定是不包含重复字符的，如果左边界还是出现了s.charAt(right),那么它的长度一定比之前的小；
while (map.getOrDefault(ch, 0) != 0) {max = Math.max(max, right - left);map.put(s.charAt(left),map.get(s.charAt(left))-1);left++;}代码：
class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();int max = 0;int left = 0;int right = 0;while (right < s.length()) {char ch = s.charAt(right);while (map.getOrDefault(ch, 0) != 0) {max = Math.max(max, right - left);map.put(s.charAt(left),map.get(s.charAt(left))-1);left++;}map.put(ch, map.getOrDefault(ch, 0) + 1);right++;}max=Math.max(max,right-left);return max;}
}2.找到最长的半重复子字符串
给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。
输入：s = "52233"
输出：4
解释：
最长的半重复子字符串是 "5223"。整个字符串 "52233" 有两个相邻的相同数字对 22 和 33，但最多只能选取一个。
思路：
滑动窗口大小未知，当相邻的相同数字存在两对的时候，此时滑动窗口就要左移；
那么左移到什么地方就可以停止了？左移到相邻的相同数字只存在一对的时候；
while(count>1){if(s.charAt(left)==s.charAt(left+1))count--;left++;}代码：
class Solution {public int longestSemiRepetitiveSubstring(String s) {int count=0;int max=0;int left=0;int right=0;while(right<s.length()){if(right>0&&s.charAt(right)==s.charAt(right-1)){count++;}while(count>1){if(s.charAt(left)==s.charAt(left+1))count--;left++;}max=Math.max(max,right-left+1);right++;}return max;}
}模板：
题目中会给出限制滑动窗口的长度的条件,然后循环遍历每一个元素，首先判断是否会对条件有影响；当不满足题目中的条件之后，就要移动滑动窗口的左边界，直至满足；
eg:第一题中是子串中不含有无重复字符；
eg:第二题中是子串中半重复字符对只可以出现一次
class Solution {public int longestSemiRepetitiveSubstring(String s) {int res=0;int left=0;int right=0;while(right<s.length()){if(题目中需要满足的条件){count++;}//如果条件不满足，就要移动左边界直至条件满足while(不满足的条件){//移动左边界}max=Math.max(max,right-left+1);right++;}return max;}
}3.数组的最大美丽值（排序+滑动窗口）
题意：
给定一个数组nums,k。数组中的每一个值都可以替换成(nums[i]-k,nums[i]+k)中的任意一个数。
数组的美丽值:数组中元素相同的个数有多少个；
求数组的最大美丽值
输入：nums = [4,6,1,2], k = 2 输出：3
4 4 1 4
思路：
这道题其实考的就是最大重叠区间，数组中每一个数组都对应了一个区间，求最大重叠区间的个数是多少。
排好序之后，判断nums[right]和nums[left]之间的差值和2*k的关系
为什么是2*k呢？因为nums[right]可以被替换成-k以内的，而nums[left]可以被替换成+k以内的，所以只要相差在2k以内，就有公共区域
代码：
class Solution {public int maximumBeauty(int[] nums, int k) {Arrays.sort(nums);int res=0;int left=0;int right=0;while(right<nums.length){if(nums[right]-nums[left]>2*k)left++;res=Math.max(res,right-left+1);right++;}return res;}
}