滑动窗口

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

题解:

• 最初采用的是哈希表加双重循环遍历从每个索引开始的最长字符串, 但这样的时间空间复杂度都特别高, 仔细观察有可以优化的地方

• 改双层循环为单层循环, 不再遍历从每个索引开始的最长字符串, 观察可得当遇到与前面字符串重复的字符#时, 从前面重复的字符#处开始即可

• public int lengthOfLongestSubstring(String s) {if(s.length() == 0 || s==null){return 0;}Map<Character, Integer> map = new HashMap<>();int max = 0;for(int i = 0, j = 0; j < s.length(); j++){while(map.containsKey(s.charAt(j))){map.remove(s.charAt(i));i++;}map.put(s.charAt(j),j);max = Math.max(max,j-i+1);// for(int j = i + 1; j < s.length(); j++){//     if(map.containsKey(s.charAt(j))){//         i = map.get(s.charAt(j));//         break;//     }else{//         map.put(s.charAt(j), j);//         temp++;//     }// }}return max;}
  

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

题解:

• 查找异位词, 如果用哈希表比较麻烦, 因为涉及该字符串出现的随机顺序,

• 由于出现的只会是小写字符, 那么可以通过$-'a’来将字符判断转换为在int[26]的数组里判断出现次数

• 首先判断两数组头部字符串是否相等–通过获取字符串第i个位置字符串-'a’的索引即可知道该字符出现频率

• 然后在长度为s.length-p.length范围内不断以1单位滑动窗口即可

• public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();int sLen = s.length();int pLen = p.length();if (sLen < pLen) {return new ArrayList<>();}int[] sCount = new int[26];int[] pCount = new int[26];for (int i = 0; i < pLen; i++) {sCount[s.charAt(i) - 'a']++;pCount[p.charAt(i) - 'a']++;}if(Arrays.equals(sCount, pCount)){res.add(0);}for(int i = 0; i<sLen-pLen;i++){sCount[s.charAt(i) - 'a']--;sCount[s.charAt(i+pLen) - 'a']++;if(Arrays.equals(sCount, pCount)){res.add(i+1);}}return res;}
  

子串

560. 和为 K 的子数组

题解:

• 方法一循环遍历每一个索引,计算子串即可, 时间复杂度O(n^2)

• 方法二, 使用前缀和, 一次遍历记录数组头到索引i的子串和, 并使用哈希表来存储该值

• 那么每到一个索引, 若该位置的前缀和p[j] 与前面位置某一索引i的前缀和p[i]只差为k, 那就是从i+1~j的子串和为k

• 采用哈希表来存储该位置的前缀和, key为前缀和, 由于数组的值可以是正数也可是负数, 会存在多个位置的前缀和为同一值, 那么value可以记录为该前缀和一共记录的次数

• 每遍历到一索引, 若该前缀和p[j]-k的值p[temp]存在于哈希表中, 那么子串的个数即为map.get(pre-k)个.

• public int subarraySum(int[] nums, int k) {// int count = 0,sum=0;// for(int i=0;i<nums.length;i++){//     sum = 0;//     for(int j = i;j<nums.length;j++){//         sum += nums[j];//         if(sum == k){//             count++;//         }//     }// }// return count;int count = 0,sum=0;Map<Integer,Integer> map = new HashMap<>();map.put(0,1);for(int i = 0;i<nums.length;i++){sum+=nums[i];if(map.containsKey(sum-k)){count+=map.get(sum-k);}map.put(sum,map.getOrDefault(sum,0)+1);}return count;}
  

239. 滑动窗口最大值

题解:

• 暴力解法在数组以及k特别大时会运行超时

• 通过暴力解法观察, 其实可以在k次比较最大值的地方优化, 如果新加入队列的值比队尾的值大, 那么此时该窗口的最大值就一定不是队尾的值了(至少都是新加入队列的值),

• 所以在元素加入队列时可以进行判断, 如果当前值>队尾元素, 移除队尾元素, 加入当前值; 如果当前值< 队尾元素, 仍需加入当前值(如果不加入当前值, 经过一段时间的滑动, 无法保证队尾元素在窗口中)

• 当需要判断当前窗口的最大值时, 从队列头获取即可, 通过队列存储的索引值来判断当前索引是否在窗口中,不在则移除直到找到元素

• 如何保证靠近队头的元素即窗口中最大值–窗口中最大值>不在窗口中的队尾元素时会移除队尾元素, 窗口中最大值<不在窗口中的队尾元素时会直接添加至队尾;

• 窗口中最大值>在窗口中的队尾元素时, 也会移除队尾元素, 窗口中非最大值遇到前方的窗口最大值时会添加在队尾

• public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new LinkedList<>();for(int i = 0;i<k;i++){while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);}int[] res = new int[n-k+1];res[0] = nums[deque.peekFirst()];for(int i = k;i<n;i++){while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);while(deque.peekFirst()<=i-k){deque.pollFirst();}res[i-k+1] = nums[deque.peekFirst()];}return res;}
  

76. 最小覆盖子串

题解:

• 用一个哈希表*HashMap<Character, Integer>*来记录滑动窗口需要的n字符的数量，对于该哈希表的值，可以分为以下三种情况：

  • HashMap<Character, Integer>
  • Integer<0 -> 滑动窗口还需要字符的数量
  • Integer==0 滑动窗口刚好包括字符的数量
  • Integer>0 滑动窗口超过n字符的数量

• 用一个变量V来记录当前已组成的字符串长度, 右指针开始移动，当遇到哈希表中存在的字符时：

  1. 如果该字符在哈希表中的值小于0，说明是滑动窗口缺少的字符，V++
  2. 递增哈希表的值

• 当V==字符串t的长度时，代表该滑动窗口包含了t字符串的所有字符（这时候可以发现哈希表中的所有值都是大于等于0的），右指针停止移动。记录此时左右指针的差值，就是当前滑动窗口的长度，取最小值。

• 此时，左指针开始移动，争取使滑动窗口长度变得更小，当遇到哈希表中存在的字符时：

  1. 递减哈希表的值
  2. 如果该字符在哈希表中的值小于0，说明滑动窗口缺少了当前左指针对应的字符，V–

• public String minWindow(String s, String t) {if (s.length() < t.length()) {return "";}HashMap<Character, Integer> count = new HashMap<>();// 统计组成t字符串的每个字符数量// count[n]<0：滑动窗口缺少多少个n字符// count[n]==0：滑动窗口刚好包含多少个n字符// count[n]>0：滑动窗口超过多少个n字符for (char c : t.toCharArray()) {count.put(c, count.getOrDefault(c, 0) - 1);}int formed = 0; // 已形成的字符数量int start = 0; // 记录最小覆盖子串的起始位置int length = Integer.MAX_VALUE; // 记录最小覆盖子串的长度for (int left = 0, right = 0, required = t.length(); right < s.length(); right++) {char c = s.charAt(right);// 更新窗口中的字符计数if (count.containsKey(c)) {if (count.get(c) < 0) {formed++;}count.put(c, count.get(c) + 1);}// 当窗口中的字符满足条件时，尝试缩小窗口while (formed == required) {if (right - left + 1 < length) {start = left;length = right - left + 1;}char d = s.charAt(left);left++;if (count.containsKey(d)) {count.put(d, count.get(d) - 1);if (count.get(d) < 0) {formed--;}}}}return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);}