一、不间断子数组(滑动窗口+哈希表)

题意：

给你一个数组nums,现在求子数组中都有 0 <= |nums[i1] - nums[i2]| <= 2 。这样称一个不间断子数组。（简而言之：子数组中最大值和最小值的差距必须<=2）。求不间断子数组的数量

输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。

思路：

1.本来试图使用int max ,int min来记录滑动窗口中的最大值和最小值，然后发现当窗口左移的时候，最大值和最小值无法更新。因此需要借助TreeMap（基于红黑树的哈希表） 帮我们自动实现升序

2.滑动窗口左移的条件是:窗口中最大值-最小值>2,左移到<=2为止

3.每次遍历结束后 收割结果：res+=right-left+1

代码：

class Solution {public long continuousSubarrays(int[] nums) {long res=0;int left=0;int right=0;TreeMap<Integer, Integer> freqMap = new TreeMap<Integer,Integer>();while(right<nums.length){//往哈希表中放值freqMap.put(nums[right],freqMap.getOrDefault(nums[right],0)+1);//如果滑动窗口不满足条件了 就要左移while(freqMap.lastKey()-freqMap.firstKey()>2){int leftNum=nums[left];freqMap.put(nums[left],freqMap.get(nums[left])-1);if(freqMap.get(nums[left])==0)freqMap.remove(nums[left]);left++;}res+=right-left+1;right++;}return res;}
}

二、单字符重复子串的最大长度

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

题意：

在给定的字符串中，只交换一次字符，求最大重复字串的长度。

思路：

要求最大重复子串的长度:xxxixxxa

1.首先找到该字符重复字串1,遇到不同的字符停止，记重复子串的长度为:len1，停止时的下标为:j

2. 从j+1开始,找到不同字符后的该字符重复子串2 记长度为:len2

因为重复子串2可以到字符串的结尾，导致后面没有字符和不同的字符做交换。

那么就要取Math.min(len1+len2+1,cnt[s.charAt(i)]）

代码：

class Solution {public int maxRepOpt1(String text) {//统计各个字符的数量int[] cnt=new int[26];for(char ch:text.toCharArray())cnt[ch-'a']++;//滑动窗口int left=0;int right=0;int size=text.length();int res=0;while(left<size){right=left;while(right<size&&text.charAt(right)==text.charAt(left)){right++;}//相等的长度为 j-i 此时j所指向的字符是不相同的int len1=right-left;int SecondRight=right+1;while(SecondRight<size&&text.charAt(SecondRight)==text.charAt(left)){SecondRight++;}//第二段字母相同的字串int len2=SecondRight-right-1;//为什么是Math.min(l+r+1,cnt[text.charAt(right)-'a'])//l+r+1(这里要求在r之后还要有该字母) 如果是这种:aaabaaa 就不行了res=Math.max(res,Math.min(len1+len2+1,cnt[text.charAt(left)-'a']));left++;}return res;}
}