二丶[最小覆盖子串](76. 最小覆盖子串 - 力扣（Leetcode）)#

思路：#

使用一个Map表示当前滑动串口亏欠t中字符的数量， key 字符 value 当前窗口中亏欠的数目，亏欠的意思是当前窗口至少还需要多少个key的字符才满足t

当left小于right的时候，我们尽可能让left向右滑动，那么什么时候left可以向右滑昵？——当前left是一个t中根本不存在的字符，或者窗口中left位置的字符数量大于t中的数量（对应下面两图）（这其实是有贪心的思想在其中的，题目是找最短的，那么left越接近right 那么越短）并且亏欠map需要同时维护

然后我们需要移动right指针，同时维护亏欠map

那么什么时候窗口中满足要求包含了t中所有字符昵——亏欠map中不存在value大于0的entry，这时候我们需要更新最佳结果

并且找到一个答案之后，我们需要left向右移动一个位置，并维护亏欠map，比如s=ADOBECODEBANC，t=ABC我们第一次找到符合的结果是ADOBEC，这时候需要left向右，因为后面存在更优秀的答案。

代码：#

class Solution {public String minWindow(String s, String t) {//逆天用例if (s == null || s.length() == 0) {return null;}if(s.length() < t.length()){return "";}char[] tCharArray = t.toCharArray();// key 字符 value 当前窗口中亏欠的数目，亏欠的意思是当前窗口至少还需要多少个key的字符才满足t// value 为正数 表示窗口欠 t，0表示互不亏欠，负数表示窗口中此字符数目多于tMap owesCharCountMap = new HashMap();//初始化亏欠的数目for (char loop : tCharArray) {owesCharCountMap.put(loop, owesCharCountMap.getOrDefault(loop, 0) + 1);}String res = null;int left = 0;int right = 0;while (right < s.length()) {//如果left对应字符是无关紧要的字符（t中不包含的字符）//或者left对应的字符那怕删掉 窗口中的字符也不会亏钱t中的字符 //满足上面任意一点 那么 left++while (left < right && !isNecessary(left, s, owesCharCountMap)) {//当前left的字符char leftChar = s.charAt(left);left++;//当前窗口亏欠窗口中多少个Integer count = owesCharCountMap.get(leftChar);//如果不为null 说明leftChar 是t中的字符 if (count != null) {//亏欠数++owesCharCountMap.put(leftChar, count + 1);}}//right位置的字符char rightChar = s.charAt(right);//right位置字符 窗口亏欠的数目Integer count = owesCharCountMap.get(rightChar);//right处字符是一个t中的字符 那么亏欠数-1if (count != null) {owesCharCountMap.put(rightChar, count - 1);}//如果窗口满足要求——指最起码不欠t中字符，及包含了所有t中的字符，那怕存在富足if (meetRequirementsOrNot(owesCharCountMap)) {//sub以下String tempRes = s.substring(left, right + 1);//记录if (res == null || tempRes.length() < res.length()) {res = tempRes;}//从窗口中 强制删除left位置处的字符//比如s=ADOBECODEBANC t = ABC 此时窗口中字符为ADOBEC 我们找到了一种结果，但是后续可能存在更好的答案//删除left位置的A 我们继续找更好的结果char leftChar = s.charAt(left);Integer leftCount = owesCharCountMap.get(leftChar);if (leftCount!=null){owesCharCountMap.put(leftChar,leftCount+1);}left++;}right++;}return res == null ? "" : res;}private boolean meetRequirementsOrNot(Map owesCharCountMap) {for (Integer v : owesCharCountMap.values()) {if (v == null) {continue;}if (v > 0) {return false;}}return true;}private boolean isNecessary(int left, String s, Map owesCharCountMap) {//left 位置的字符char leftChar = s.charAt(left);//当前亏欠map中的对应的亏欠数目Integer count = owesCharCountMap.get(leftChar);//为null 说明这个字符都不是t字符串中的字符 那么说明left位置的字符没必要存在于窗口中if (count == null) {return false;}//如果大于等于0 说明当前亏欠这个字符， 或者刚刚好，//如果移动那么窗口中的字符数将不够覆盖t中所有字符if (count >= 0) {return true;}//说明left处的字符不是必要的//说明 当前窗口中这个字符的数量已经大于t中这个字符的数量return false;}}

三丶[串联所有单词的子串](30. 串联所有单词的子串 - 力扣（Leetcode）)#

思路：#

我的思路其实和第二题一样，也是恢复一个亏欠map 然后进行滑动窗口，只是这个开始滑动的位置应该是1~单个单词长度这个范围都进行滑动窗口，这一点很关键。

然后我们需要处理两种情况

• 滑动窗口中包含了 words中不存在的单词 ，那么前功尽弃，我们需要从这个不存在单词的结尾继续滑动
• 滑动窗口中包含单词1的数量大于了words数组中单词1的数量，那么其实我们应该从第一个出现单词1位置的下一个位置开始滑动

这个题推荐看题解30. 串联所有单词的子串 - 力扣（Leetcode）我的解法并不是很优秀

代码：#

class Solution {public List findSubstring(String s, String[] words) {List res = new ArrayList<>();int singleWordLen = words[0].length();if (singleWordLen * words.length > s.length()) {return res;}//亏欠mapMap owensMap = new HashMap<>();for (String loop : words) {owensMap.put(loop, owensMap.getOrDefault(loop, 0) + 1);}int roundStartPos = 0;//从第一个位置开始 ，第二个位置开始 。。到单个单词长度个位置  while (roundStartPos < singleWordLen) {Map owensMapTemp = new HashMap<>(owensMap);int left = roundStartPos;int right = roundStartPos;//滑动窗口while (right <= s.length() - singleWordLen) {//left 位置的单词 不是必要的while (left < right && !isNecessary(left, singleWordLen, s, owensMapTemp)) {String temp = s.substring(left, left + singleWordLen);Integer count = owensMapTemp.get(temp);if (count != null) {owensMapTemp.put(temp, count + 1);}left += singleWordLen;}//right位置的单词String rightString = s.substring(right, right + singleWordLen);Integer count = owensMapTemp.get(rightString);//right位置的单词 是我们需要的 那么维护亏欠mapif (count != null && count >= 1) {owensMapTemp.put(rightString, count - 1);right += singleWordLen;} else {//right 位置的单词 不是words数组中的单词 那么直接然后right 跨过这个单词，直接从下一个单词开始if (count == null) {right = right + singleWordLen;left = right;owensMapTemp = new HashMap<>(owensMap);} else {//right位置的单词是words数组中的单词 但是当前窗口中这个单词数量 已经 大于words数组中这个单词数量的单词//那么删除头部的第一个单词 然后继续，String temp = s.substring(left, left + singleWordLen);Integer tempCount = owensMapTemp.get(temp);if (tempCount != null) {owensMapTemp.put(temp, tempCount + 1);}left += singleWordLen;}}//符合要求 那么left 移动到下一个单词 并继续 找出所有答案if (meetRequire(owensMapTemp)) {res.add(left);String temp = s.substring(left, left + singleWordLen);Integer tempCount = owensMapTemp.get(temp);if (tempCount != null) {owensMapTemp.put(temp, tempCount + 1);}left += singleWordLen;}}roundStartPos++;}return res;}private boolean isNecessary(int left, int singleWordLen, String s, Map owensMapTemp) {String temp = s.substring(left, left + singleWordLen);Integer count = owensMapTemp.get(temp);if (count == null) {return false;}if (count < 0) {return false;}return true;}private boolean meetRequire(Map owensMapTemp) {for (Integer c : owensMapTemp.values()) {if (c == null) {continue;}if (c > 0) {return false;}}return true;}}

四丶[重复的DNA序列](187. 重复的DNA序列 - 力扣（Leetcode）)#

思路：#

这个题挺逆天的，很难想到怎么用滑动窗口做，使用2进制表示字母A，C，G，T，分别使用00，01，02，03，这样窗口滑动的时候就是第一个字母出去，意味着二进制表示左移位2，右边字符进来，使用位操作

代码：#

class Solution {public List findRepeatedDnaSequences(String s) {if(s == null || s.length()<=10){return new ArrayList<>();}List res =  new LinkedList<>();Map memory = new  HashMap();int right = 0;int firstBi = 0;while(right<10){firstBi = (firstBi<<2)| binaryOf(s.charAt(right));right++;}memory.put(firstBi,1);while(right < s.length()){int bi = binaryOf(s.charAt(right));//左边字符出去  右边字符进来firstBi = ((firstBi<<2) |bi)&((1<<20)-1);;int count =memory.getOrDefault(firstBi,0)+1;memory.put(firstBi,count);if(count == 2){res.add(s.substring(right+1-10,right+1));}right++;}return res;}private int binaryOf(char a){if(a == 'A'){return 0;}if(a == 'C'){return 1;}if(a == 'G'){return 2;}if(a == 'T'){return 3;}return -1;}
}

五丶[长度最小的子数组](209. 长度最小的子数组 - 力扣（Leetcode）)#

思路：太简单了，窗口描述当前子数据，使用sum记录当前和，如果大于target那么更新长度，如果减去左边界的值还能大于，那么left++。直到right到 数组边界

class Solution {public int minSubArrayLen(int target, int[] nums) {if(nums == null||nums.length == 0){return 0;}int left = 0;int right = 1;int sum =nums[0];int minLen = sum>target?1:0;;while(right=target){sum -= nums[left];left++;}if(sum>=target){if(minLen == 0||minLen>right-left+1){minLen = right - left+1;}}right++;}return minLen;}
}

六丶[存在重复元素 II](219. 存在重复元素 II - 力扣（Leetcode）)#

思路：#

维护一个长度为k的滑动窗口，使用set记录窗口中的数字，每次left位置的数据从窗口中出去，right位置的数进来，首先删除set中left代表的数字，然后如果right位置的数字存在于set中那么说明重复

代码：#

  public boolean containsNearbyDuplicate(int[] nums, int k) {if(nums == null || nums.length<=1){return false;}if(k == 0){return false;}int left = 0;int right = 0;Setmemory = new HashSet();while(right

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {if (nums == null || nums.length == 0) {return false;}if (indexDiff == 0) {return false;}TreeSet ts = new TreeSet<>();int left = 0;int right = 0;while (right < indexDiff + 1 && right < nums.length) {if (exist(ts,nums[right],valueDiff)){return true;}ts.add(nums[right]);right++;}while (right < nums.length) {ts.remove(nums[left++]);if (exist(ts,nums[right],valueDiff)){return true;}ts.add(nums[right++]);}return false;}private boolean exist(TreeSet ts, int value, int diff) {//Set中是否 存在一个数A 满足 abs(A-value)<=diff//A>=value 最小的数 min 是否满足 min - value <= diff//A<=value 最大的数max 是否满足 value - max<= diffInteger min = ts.ceiling(value);if (min != null && min - value <= diff) {return true;}Integer max = ts.floor(value);if(max!=null&&value - max<=diff){return true;}return false;}}

 public int[] maxSlidingWindow(int[] nums, int k) {//优先队列 维护滑动窗口中的最大值if(nums == null || nums.length < k ){return nums;}int[]res = new int[nums.length - k +1]; //优先使用值进行比较，值越大越在堆顶//其次使用下标进行比较，下表越大越在堆顶，下标越大 活得越久PriorityQueue q = new PriorityQueue<>((i,j)->i[0]!=j[0]?j[0]-i[0]:j[1]-i[1]);int right = 0;while(right

 public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null ){return nums;}int[]res = new int[nums.length - k +1];//队列中的值是下标 但是必须保证这些下标值是单调递减的//当前 i=nums[i] 这时候num[i]对应下标 不需要维护了//说是单调栈其实是双向队列，因为我们需要看栈底元素LinkedList ll = new LinkedList();int right = 0;//初始化双端队列while(right < k){//nums[ll.getLast()] <= nums[right]//对应 1，2，3，4 k =3 初始化的时候 【1，2，3】4 这时候我们只需要维护3即可while(!ll.isEmpty() && nums[ll.getLast()] <= nums[right]){ll.removeLast();}ll.addLast(right);right++;}res[0] = nums[ll.getFirst()];int count = 1;while(right < nums.length){//同上while(!ll.isEmpty() && nums[ll.getLast()] <= nums[right]){ll.removeLast();}ll.addLast(right);//如果队列头 也就是最大的值 将不处于窗口外while(ll.getFirst() <= right-k){ll.removeFirst();}res[count++] = nums[ll.getFirst()];right++;}return res;}

class Solution {public List findAnagrams(String s, String p) {if(s == null || s.length()();}List res = new ArrayList<>();if(s.equals(p)){res.add(0);return res;}//记录p中的字符和对应的数量，因为都是小写字母，26长度的数组足以int[] pCharCount = new int[26];for(int i= 0; i p.length()){windowCharCount[s.charAt(left)-'a']--;left++;}//右边界++windowCharCount[s.charAt(right)-'a']++;//字符和数目 和p一样if(meetRequire(pCharCount,windowCharCount)){res.add(left);}right++;}return res;}private boolean meetRequire(int[] pCharCount,int[] windowCharCount ){for(int i =0;i<26;i++){if(pCharCount[i]!=windowCharCount[i]){return false;}}return true;}
}

class Solution {public int characterReplacement(String s, int k) {if(s == null ){return 0;}if(s.length() <=k){return s.length();}int res = 0;int left = 0;int right = 0;int[]charCount = new int[26];while(right