滑动窗口模块

滑动窗口类问题：总能找到一个窗口，从前往后移动来查找结果值。

这个窗口的大小可能是固定的，也可能是变化的。但窗口的大小一定是有限的。

https://www.cnblogs.com/huansky/p/13488234.html

Leetcode 3. 无重复字符的最长子串

题意理解：

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

        我们采用滑动窗口来解决这道问题，其中：滑动窗口用来查找不重复子串。

解题思路：

        找到一个位置i，开始扩展滑动窗口，len++,当出现重复元素时，记录不重复子串长度，i位置向后移一位。

1.滑动窗口解题

public int lengthOfLongestSubstring(String s) {int maxLen=0;HashSet<Character> set=new HashSet<>();for(int i=0;i<s.length();i++){int j=i;while(j<s.length()&&(!set.contains(s.charAt(j)))){set.add(s.charAt(j));j++;}maxLen=Math.max(maxLen,set.size());set=new HashSet<>();}return maxLen;}

2.复杂度分析

时间复杂度：O(n^2),遍历元素和遍历滑动窗口的时间耗费

空间复杂度：O(n), 所有set的空间损耗。

Leetcode 438. 找到字符串中所有字母异位词

题意理解：

        给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串)。

        

        给定一个目标字符串p，在字符串s中寻找其异位词的位置下标。

        则s中存在和p相同长度的子串，且子串的组成相同，返回该子串的位置即可。

        此处采用滑动窗口来解题。

解题思路：

        采用滑动窗口解题，其中窗口大小等于p的长度

        将窗口从0下标开始向后移动，每次取窗口里的子串进行判断        

        窗口子串是否是p的异位词

        是怎将窗口位置下标加入结果集，否则不加入

        将窗口继续向后移动。

1.滑动窗口解题

    public List<Integer> findAnagrams(String s, String p) {List<Integer> result=new ArrayList<>();int window=p.length();for(int i=0;i<s.length()-window+1;i++){String str=s.substring(i,i+window);if(isAllotopicWord(str,p)){result.add(i);}}return  result;}public boolean isAllotopicWord(String str,String target){int[] letter=new int[26];for(int i=0;i<str.length();i++)letter[str.charAt(i)-'a']+=1;for(int i=0;i<target.length();i++)letter[target.charAt(i)-'a']-=1;for(int i=0;i<letter.length;i++)if(letter[i]!=0) return false;return true;}

2.复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(n)

子串模块

子串：

子串类题目通常解决方法有：滑动窗口、双指针等

特别要注意一些边界判断，容易出错

再就是如何优化时间|空间复杂度。

Leetcode 560. 和为 K 的子数组

题意理解：

        给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

        查找有多少个连续的子序列和为k。是子串遍历的一类问题。

解题思路：

        遍历所有的连续子串，若子串长度==k,则result++

        特别的注意：

        当子串和大于k时，不代表遍历停止，后续的负数可能使其仍然满足一个子串。

        如：1，-1，0

        k=0

        则满足规则的子串有： 1，-1          1，-1，0           0

1.子串遍历解题

public int subarraySum(int[] nums, int k) {int result=0;for(int i=0;i<nums.length;i++){int sum=0;for(int j=i;j<nums.length;j++){sum+=nums[j];if(sum==k) result++;}}return  result;}

2.复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(1)

Leetcode 239. 滑动窗口最大值

题意理解：  

        给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

解题思路：

        选中一个1起始位置，如0, 则获得第一个滑动窗口： 1，3 ，-1   此时max=3

        向下滑动一个位置，此时要有一个数加入，一个数被丢弃

        使用队列来维持窗口中的最大值。使最大值总是出现在队列尾端。

        比最大值小的值维护在，队首。

这道题目的难点在于：最大的数被移出窗口后，如何从剩下的值中获得最大值

还一个点：（关键）

1.  k个数的数列，其中包含最大值x，则x以前的数是没有意义的：
2. 因为只要能取到x, 一定不会取到x之前的数，因为x最为max，一定比前面的值大
3. 除此之外：
4. 新进入的值y:  y前面比它小的值也是没有意义的，若y比x大，则y前面所有的值都是没有意义的废数。

这样的解法本质上是将滑动窗口里的值维护到了一个单调队列里，他总是保持最大值及到当前位置的比它小的值，最大值前面且比它小的数是废数。

1.滑动窗口解题

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length==1||k==1){return nums;}Deque<Integer> queue=new LinkedList<>();List<Integer> numbers=new ArrayList<>();for(int i=0;i<nums.length;i++){//弹出过期数据if((!queue.isEmpty())&&queue.peekFirst()==i-k){queue.pollFirst();}//前面比它大if(queue.isEmpty()){queue.offerLast(i);} else if(nums[queue.peekLast()]>nums[i]) {queue.offerLast(i);}else if(nums[queue.peekLast()]<=nums[i]){//前面比它小，全部弹出while((!queue.isEmpty())&&nums[queue.peekLast()]<=nums[i]){queue.pollLast();}queue.offerLast(i);}if(i>=k-1){numbers.add(queue.peekFirst());}}int[] result=new int[numbers.size()];for(int i=0;i<numbers.size();i++){result[i]=nums[numbers.get(i)];}return result;}
}

2.复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

Leetcode 76. 最小覆盖子串

题意理解：

        给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

如果 s 中存在这样的子串，我们保证它是唯一的答案

        及返回s中包含t所有元素的最短子串。此处还是可以用双指针来解决这道题目。

解题思路：

        1.找到一个左指针开头： 即一个t中的元素开头。

        2.找到一个右指针结尾： 即一个t中的元素结尾，且当前滑动窗口包含t中所有元素。

        3.将结果维护在result串中

        4.左指针向右移动，弹出左侧元素，直到左侧开始第一个t中元素

        5.右指针扩展，右边找滑动窗口的结尾。

        6.重复步骤3

一个要注意的点：如何判断s包含t所有元素呢？t中可能有重复元素

比较两个方面：是否右t中元素，s中的对应t中的元素个数要多于或等于t中对应元素的个数

如：s: abcab     t:aab   s中a的个数>=t中a的个数，才能满足条件：s包含t所有元素

上述方法没问题，但是会发生超时问题：优化

还是left和right两个指针

1.right向右拓展，left向right靠近，最终获得最短符合条件的子串

2.用sMap和tMap来维护子串和t串的元素及个数

3.判断tMap所有key满足：sMap.get(c)>tMap.get(c)，则[left,right]子串满足要求

4.将结果子串用ansL和ansR维护，其中表示子串的最左位置和最右位置

5.最后返回[ansL,ansR]子串

优化了哪里：

        sMap由right和left实时维护，不用每次在对[left,right]统计，少了一层for循环

        时间复杂度优化了

1.双指针解题

class Solution {public String minWindow(String s, String t) {int ansL=0,ansR=-1;//保存t中元素及个数|sMap<Character,Integer> tMap=new HashMap<>();Map<Character,Integer> sMap=new HashMap<>();for(char c:t.toCharArray()){tMap.put(c,tMap.getOrDefault(c,0)+1);}int left=0,right=0;while(right<s.length()){if(tMap.containsKey(s.charAt(right)))sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);while(left<=right&&isContains(sMap,tMap)){//right向右移动，left向right缩，最后获得最短子串if(ansR==-1||right-left<ansR-ansL) {ansL=left;ansR=right;}if(tMap.containsKey(s.charAt(left))){sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);}left++;}right++;}return ansR-ansL+1<=0?"":s.substring(ansL,ansR+1);}//判断public boolean isContains(Map<Character,Integer> sMap,Map<Character,Integer> tMap){for(char key:tMap.keySet()){if(tMap.get(key)>sMap.getOrDefault(key,0)) return false;}return true;}
}

2.复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(n)

这道题是一道困难题：难在容易超时。如何对代码优化。