滑动窗口套路：

        核心套路三步骤：

                1.入： 下标为 i 的元素进入窗口，更新相关统计量(因为一个元素进入了，则相关统计的数据要更新，就是+)，然后进行判断，如果i < k - 1 则continue，继续进入窗口，因为定长窗口元素不足；

                2.更新：更新答案。一般是更新最大\最小值；

                3.出：下标为i - k + 1 的元素离开窗口，更新相关统计量(出了一个元素，窗口内的统计量要减去这个出的元素)。

一：定长滑动窗口

1.定长字串中元音的最大数目

        元音有：a\e\i\o\u

        给你字符串 S 和整数 k；

        请你返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

class Solution {public int maxVowels(String s, int k) {int max = Integer.MIN_VALUE;int sum = 0;char[] arr = s.toCharArray();for (int i = 0; i < arr.length; i++) {//入if (isVowel(arr[i])) sum++;if (i < k - 1) continue;//更新max = Math.max(sum, max);//出char out = arr[i - k + 1];if (isVowel(out)) sum--;}return max;}public boolean isVowel(char ch) {return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';}
}

2.子数组最大平均数I

        给你一个由 n 个元素组成的整数数组 nums 和一个整数 k

        请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均值

        任何误差小于 10(-5)的答案都将被视为正确答案

class Solution {public double findMaxAverage(int[] nums, int k) {int maxAvg = Integer.MIN_VALUE, sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];if (i < k - 1) continue;maxAvg = Math.max(maxAvg, sum);sum -= nums[i - k + 1];}return 1.0 * maxAvg / k;}
}

3.大小为 k 且平均值大于等于阈值的子数组数目

        给你一个整数数组 arr 和两个整数 k 和threshold

        请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

class Solution {public int numOfSubarrays(int[] arr, int k, int threshold) {int avg = 0, count = 0;for (int i = 0; i < arr.length; i++) {avg += arr[i];if (i < k - 1) continue;if (avg / k >= threshold) count++;avg -= arr[i - k + 1];}return count;}
}

4.得到 K 个黑块的最少涂色次数

        给你一个长度为 n 下标从 0 开始的字符串 blocks，blocks[i] 要么是 ‘W’ 要么是 ‘B’，表示白色和黑色

        给你一个整数 k，表示想要连续黑色快的数目

        每一次操作中，你可以选择一个白色快将它涂成黑色快

        请你返回至少出现一次连续 k个黑色快的最少操作次数

class Solution {public int minimumRecolors(String blocks, int k) {int min = Integer.MAX_VALUE, count = 0;char [] arr = blocks.toCharArray();for (int i = 0; i < arr.length; i++) {if (arr[i] == 'W') count++;if (i < k - 1) continue;min = Math.min(min, count);char out = arr[i - k + 1];if (out == 'W') count--;}return min;}
}

二：不定长滑动窗口

1.无重复字符的最长字串

        给定一个字符串 s，请你找出其中不含有重复字符的最长字串的长度。

class Solution {public int lengthOfLongestSubstring(String s) {//用哈希表或者数组存重复字符的上一个索引Map<Character, Integer> map = new HashMap<>();char[] arr = s.toCharArray();int left = -1;  //开始从-1开始 表示没有重复元素int len = 0;for (int i = 0; i < arr.length; i++) {if (map.containsKey(arr[i])) {  //有重复的 那么就将left起点从上一个重复的为止开始算长度left = Math.max(left, map.get(arr[i])); //这是防止多个重复 比如 abba b先重复了 left已经再1了 这个时候a//重复了 a的上一个位置还在0 但是不能从0开始算 要从1开始算}//更新最新字符的索引map.put(arr[i], i);len = Math.max(len, i - left);}return len;}
}

2.每个字符最多出现两次的最长子字符串

        给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串

        并返回该子字符串的最大长度

class Solution {public int maximumLengthSubstring(String s) {//这特么是简单题？ /**不定长滑动窗口 因为这题说了是由小写字母组成 可以用阿斯克吗来做或者用哈希？想一想哈希的做法*/// Map<Character, Integer> map = new HashMap<>();// int len = 0, left = 0;// char[] arr = s.toCharArray();// for (int i = 0; i < arr.length; i++) {//     map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);//     while (map.get(arr[i]) > 2) {//         //去掉重复字符的第一个//         map.put(arr[left], map.get(arr[left]) - 1);//         left++;//     }//     len = Math.max(len, i - left + 1);// }// return len;//用数组来做 效率一点int[] arr = new int[26];char[] c = s.toCharArray();int len = 0, left = 0;for (int i = 0; i < c.length; i++) {int j = c[i] - 'a'; //正好对应索引下标a从0开始arr[j]++;while (arr[j] > 2) {arr[c[left++] - 'a']--; //不管元素是什么，只要保证left从0开始遍历，一直到找到j这个元素 然后删掉它//这个时候的left++就是新的开端 就是找到第一个重复的元素 删掉他 然后从它下一个开始}len = Math.max(len, i - left + 1);}return len;}
}

    3.删掉一个元素以后全为 1 的最长子数组 

            给你一个二进制数组 nums，你需要从中删掉一个元素

                请你在删掉元素的结果数组种，返回最长的且只包含1的非空子数组的长度

                如果不存在这样的子数组，请返回0

class Solution {public int longestSubarray(int[] nums) {int len = 0, sum = 0, left = 0;for (int i = 0; i < nums.length; i++) {sum += 1- nums[i];  //如果是0 那么肯定是+1了 相当于判断是否是0while (sum > 1) {//表示最少进来了两个0了，那么需要删掉最开始的那个0sum -= 1- nums[left++];}len = Math.max(len, i - left);}return len;}
}

二.相向双指针

两个指针left=0，right = n - 1，从数组的两端开始，向中间移动，这叫相向双指针。

1.反转字符串

        编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出

        不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用0(1)的额外空间解决

        这一问题

class Solution {public void reverseString(char[] s) {/**双指针？ 从左和从右开始同时移动，然后右边和左边的值互换然后当左>=右了就停下 */int left = 0, right = s.length - 1;while (left < right) {char temp = s[left];s[left++] = s[right];s[right--] = temp;} }
}

2.验证回文串

        如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读

        和反着读都一样。则可以认为改短语是一个 回文串

        字母和数字都属于字母数字字符

        给你一个字符串 s，如果它是回文串，返回true，否则返回false

class Solution {public boolean isPalindrome(String s) {//先大写转小写， 然后去掉非字母数字字符 用ascii码//字母ASCII码是97-122 数字0-9的ASCII码是48到57s = s.toLowerCase();StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if ((c >= 48 && c <= 57) || (c >= 97 && c <= 122)) {sb.append(c);}}//验证回文串int left = 0, right = sb.length() - 1;String str = sb.toString();while (left < right) {char c = str.charAt(left);if (str.charAt(left++) != str.charAt(right--)) return false;}return true;}
}

3.删除字符串两端相同字符后的最短长度

        给你一个只包含字符 ‘a’、‘b’、'c' 的字符串 s，你可以执行下面这个操作任意次：

        1.选择字符串 s的一个非空的前缀，这个前缀的所有字符都相同

        2.选择字符串 s的一个非空的后缀，这个后缀的所有字符都相同

        3.前缀和后缀在字符串种任意位置都不能有交集

        4.前缀和后缀包含的所有字符都要相同

        5.同时删除前缀和后缀

        请你返回堆字符串 s 执行上面操作任意次以后(可能是0次)，能得到的最短长度

class Solution {public int minimumLength(String s) {/**就是前后消消乐，只要前后有相同的字符就全删掉，然后没有相同了就返回剩下的字符串长度双指针，前后相同的话，left++ 一直到不相同或者left和right相遇了同理 right-- 一直到不相同或者和left相遇最后计算right和left的长度+1 因为是表示索引 length是相减+1*/int left = 0, right = s.length() - 1;while (left < right && s.charAt(left) == s.charAt(right)) {char c = s.charAt(left);while (left <= right && s.charAt(left) == c) left++;while (left <= right && s.charAt(right) == c) right--;}return right - left + 1;}
}

4. 有序数组的平方

        给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，

        要求也按 非递减顺序 。

class Solution {public int[] sortedSquares(int[] nums) {int left = 0, right = nums.length - 1;int[] arr = new int[nums.length];for (int i = nums.length - 1; i >= 0; i--) {int l = nums[left] * nums[left];int r = nums[right] * nums[right];if (l > r) {arr[i] = l;left++;} else {arr[i] = r;right--;}}return arr;}
}

5.两数之和II -输入有序数组

        给你一个下标从 1 开始的证书数组 numbers，该数组已按 非递减顺序排列，请你从数组种

        找到满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]

        和 numbers[index2]，则 1<= index1 < index2 <= numbers.length

        以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2

        你可以假设每个输入 只对应唯一的答案，而且你 不可以重复使用相同的元素

        你所涉及的解决方案必须只能使用常量级的额外空间。 

class Solution {public int[] twoSum(int[] numbers, int target) {//使用哈希// Map<Integer, Integer> map = new HashMap<>();// for (int i = 0; i < numbers.length; i++) {//     int right = target - numbers[i];//     if (map.containsKey(right)) {//         return new int[]{i + 1, map.get(right)};//     }//     map.put(numbers[i], i + 1);// }// return null;//优化 因为是需要输出有序int left = 0, right = numbers.length - 1;int[] arr = new int[2];while (left < right) {int temp = numbers[left] + numbers[right];if (target == temp ) break;if (temp < target) {left++;} else {right--;}}arr[0] = left + 1;arr[1] = right + 1;return arr;}
}

6.平方数之和

        给定一个非负整数 c，判断是否存在两个整数 a 和 b，使得 a2 + b2 = c

class Solution {public boolean judgeSquareSum(int c) {//想象成两数之和  用c的根作为基数来判断int a = 0, b = (int)Math.sqrt(c);while (a <= b) {if (a * a == c - b * b) return true;if (a * a < c - b * b) {a++;} else {b--;}}return false;}
}

7.统计和小于目标的下标对数目

        给你一个下标从 0 开始长度为 n的整数数组 nums 和一个整数target，请你返回

        满足 0 <= i < j < n且 nums[i] + nums[j] < target的下标对(i, j) 的数目

class Solution {public int countPairs(List<Integer> nums, int target) {//因为只是输出对数 不需要index 所以排序之和不影响Collections.sort(nums);int count = 0, left = 0, right = nums.size() - 1;while (left < right) {if (nums.get(left) + nums.get(right) < target) {//因为排序了 所以这个区间内的对数都满足count += right - left;left++;} else {right--;}}return count;}
}

8.三数之和

        给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足

        i != j、i != k 且 j != k，满足还满足 nums[i] + nums[j] + nums[k] == 0。

        请你返回所有和为 0 且不重复的三元组、

        注意：答案中不可以包含重复的三元组。

class Solution {public List<List<Integer>> threeSum(int[] nums) {/**固定指针+双指针 从0开始 然后left=i+1 right = n-1先排序 接下来就是先判断重复的情况i = i + 1 则continue i++left = left +1 left++right = right-1 right--然后满足 i+left+right = 0 left++ right--如果 < 0 left++ >0 right--*/List<List<Integer>> lists = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {if (nums[i] > 0 ) return lists;if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);lists.add(list);while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;} else if (sum < 0) {left++;} else {right--;}}}return lists;}
}

三.同向双指针

        两个指针的移动方向相同

1.最短无序连续子数组

        给你一个整数数组 nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，

        那么整个数组都会变成升序排序

        请你找出符合题意得 最短 子数组，并输出它得长度。

class Solution {public int findUnsortedSubarray(int[] nums) {/**边界双指针解法可以把数组抽象成三段，前、中、后前的长度>=0 这段肯定是有序的中的长度>=0 这段肯定是无序的后的长度>=0 这段肯定是有序的目的就是找出中段的长度 最极限的情况就是要么是0要么是整个数组的length怎么确定中段范围呢，找出两个临界值 begin和end从begin开始，begin前面的都是比begin小的，begin后面的begin+1肯定是大于begin的 无序的开始然后到end结束，end后面的肯定都是比end大的然后中段的长度就是end-begin+1 算长度都需要+1   begin从右到左遍历 确定begin的位置end从左到右遍历 确定end的位置*/int len = nums.length;int min = nums[len - 1], begin = 0;int max = nums[0], end = -1;       for (int i = 0; i < len; i++) {//从左右到算endif (nums[i] < max) {end = i;                } else {max = nums[i];}//从右到左算beginif (nums[len - i - 1] > min) {begin = len - i - 1;               } else {min = nums[len - i - 1];}}return end - begin + 1;}
}

四.双序列双指针

1.合并两个有序数组

        给你两个按 非递减顺序 排列的整数数组 nums1和nums2，另外有两个整数 m 和 n，分别

        表示 nums1和nums2中的元素数目

        请你合并 nums2到nums1中，使得合并后的数组同样按 非递减顺序 排列

        注意：最终合并后的数组不应由函数返回，而是存储在nums1中，为了应对这种情况

        nums1的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为0

        应忽略，nums2的长度为n。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {/**因为nums1和nums2已经是递增排序过了的所以换个角度，从大到小开始插入，因为nums1的后面肯定是空的 所以从尾部插入大的谁大先插入谁 然后指针--*/int a = m - 1, b = n - 1;int max = m + n - 1;while (b >= 0) {    //因为是nums2插入nums1所以最后结束肯定nums已经空了才算完成插入//大的插入if (a >= 0 && nums1[a] > nums2[b]) {nums1[max--] = nums1[a--];} else {nums1[max--] = nums2[b--];}}}
}

2.判断子序列

        给定字符串 s 和 t，判断s是否为 t的子序列

        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符

        相对位置形成的新字符串

        例如：“ace”是“ancde”的一个子序列，而“aec”并不是

class Solution {public boolean isSubsequence(String s, String t) {/**双指针 一个从s0开始 一个从t0开始相等 都++不等 s原地等候 t++最后s=s.length或者t=t.length退出循环最后判断 s==s.length ==就是走完了 那么肯定是字串*/int sIndex = 0, tIndex = 0;while (sIndex < s.length() && tIndex < t.length()) {if (s.charAt(sIndex) == t.charAt(tIndex)) {sIndex++;tIndex++;} else {tIndex++;}}return sIndex == s.length();}
}