xicheng

V1

2022/11/11阅读:12主题:默认主题

数组-滑动窗口(直接套模板完事儿)

前言

兄弟们,互联网寒冬期,算法刷着走。上篇文章讲了双指针的左右指针,双指针是数组类算法题中最重要的一个分支之一。这篇文章讲双指针技巧的滑动窗口。遇到双指针的题目,直接套用模板就完事儿。另外,数组有下图这些知识点与技巧。

思路

滑动窗口一般用于解决主串是否满足子串的某些需求问题,比如,是否包含某个字串,是否含有字串的所有字符等。 滑动窗口有固定的解题模板。但是细节众多,需要反复练习。

//s为原字符串,t为子字符串
public void slidingWindow(String s, String t) {
    //初始化窗口应该满足的条件needMap,key=子串t中的字符,value=字符在t字符串中出现的次数
    Map<Character, Integer> needMap = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        Character k = t.charAt(i);
        needMap.put(k, needMap.getOrDefault(k, 0) + 1);
    }
    //滑动窗口中包含的字符,及其数量,key=滑动窗口中的字符,value=字符出现的次数
    Map<Character, Integer> winMap = new HashMap<>();
    //l:窗口左指针,r窗口右指针,validCount:窗口中有多少个字符满足了条件。
    int l = 0, r = 0, validCount = 0;
    while (r < s.length()) {
        //即将加入窗口的字符
        char in = s.charAt(r);
        //窗口右指针右移
        r++;
        //进行窗口内数据的操作
        ...
        while (窗口是否应该收缩) {
            //即将从窗口移除的字符
            char out = s.charAt(l);
            //窗口左指针右移
            l++;
            //进行窗口内数据的操作
            ...
        }
    }
}

最小覆盖子串

leetcode第76题

解题思路

套用滑动窗口模板。窗口左右指针下标从0开始遍历原字符串。

窗口的右指针右移后,判断加入窗口的字符是否是子串的字符,若是则更新winMap。更新后若winMap中该字符的value=needMap中该字符的value,说明滑动窗口中该字符数量与子串该字符的数量相等,则validCount+1。

当validCount=needMap.size()时,说明子串中的字符全部都包含在了滑动窗口中,且每个字符的字符数量也满足。这时就把窗口的左指针右移,直到窗口中的字符串不在符合要求为止。

重复上述步骤,找出最小的窗口。

复杂度分析

时间复杂度:O(nlogz+mlogz),z是字符集的大小,n是原字符串的长度,m是子串长度。最坏情况下,窗口右指针会扫描一遍原数组,窗口左指针会扫描一边原数组,所以最多扫描2n次,而每扫描一次,就有若干次的map.get与map.put,则复杂度是nlogz。初始化needMap时,需要扫描一遍子串,且也有map.get与map.put。则复杂度为O(nlogz + mlogz)。

空间复杂度:O(z)。因为需要建立两个map分别存滑动窗口与字串中字符的出现次数,且每个map的键值对最多不会存放超过字符集的大小。

代码

class Solution {
    public String minWindow(String s, String t) {
      Map<Character, Integer> needMap = new HashMap<>();
      for (int i = 0; i < t.length(); i++) {
         Character k = t.charAt(i);
         needMap.put(k, needMap.getOrDefault(k, 0) + 1);
      }
      Map<Character, Integer> winMap = new HashMap<>();
      int l = 0, r = 0, validCount = 0, start = 0, minWin = Integer.MAX_VALUE;
      while (r < s.length()) {
         char in = s.charAt(r);
         r++;
         if (needMap.containsKey(in)) {
            winMap.put(in, winMap.getOrDefault(in, 0) + 1);
            //窗口中该字符的数量等于字串中该字符的数量
            if (winMap.get(in).equals(needMap.get(in))) {
               validCount++;
            }
         }
         //窗口中所有字符的数量都大于等于字串中字符的相应数量,说明这是一个满足题意的子串
         while (validCount == needMap.size()) {
             //记录满足条件时的最小窗口
            if (r - l < minWin) {
               start = l;
               minWin = r - l;
            }
            char out = s.charAt(l);
            l++;
            if (needMap.containsKey(out)) {
               winMap.put(out, winMap.getOrDefault(out, 0) - 1);
               //当窗口中该字符的数量小于了字串中的数量
               if (winMap.get(out) < needMap.get(out)) {
                  validCount--;
               }
            }
         }
      }
      return Integer.MAX_VALUE == minWin ? "" : s.substring(start, start + minWin);
   }
}

字符串的排列

leetcode第567题

解题思路

套用滑动窗口模板。窗口左右指针下标从0开始去遍历s2。

窗口的右指针右移后,判断加入窗口的字符是否是s1的字符,若是则更新winMap。更新后若winMap中该字符的value=needMap中该字符的value,说明滑动窗口中该字符数量与s1中的该字符的数量相等,则validCount+1。

当validCount=needMap.size()时,说明s1中的字符全部都包含在了滑动窗口中。此时进行判断,当窗口的长度=s1的长度时,说明是一个合法序列,则返回true。

重复上述步骤,若遍历结束后都没找到合法序列,则返回false。

复杂度分析

时间复杂度:O(nlogz + mlogz),z是字符集的大小。n 是s1字符串的长度,m是s2字串长度。最坏情况下,窗口右指针会扫描一遍s2,窗口左指针会扫描一遍s2,所以最多扫描2m次,而每扫描一次,就用若干次的map.get与map.put,则复杂度是mlogz。初始化needMap时,需要扫描一遍s1,每次扫描也有map.get与map.put。则复杂度为O(nlogz + mlogz)。

空间复杂度:O(z)。因为需要建立两个map分别存滑动窗口与字串中字符的出现次数,且每个map的键值对最多不会存放超过字符集的大小。

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
      Map<Character, Integer> needMap = new HashMap<>();
      for (int i = 0; i < s1.length(); i++) {
         Character k = s1.charAt(i);
         needMap.put(k, needMap.getOrDefault(k, 0) + 1);
      }

      Map<Character, Integer> winMap = new HashMap<>();
      int l = 0, r = 0, validCount = 0;
      while (r < s2.length()) {
         char in = s2.charAt(r);
         r++;
         if (needMap.containsKey(in)) {
            winMap.put(in, winMap.getOrDefault(in, 0) + 1);
            if (winMap.get(in).equals(needMap.get(in))) {
               validCount++;
            }
         }
         while (validCount == needMap.size()) {
            if (r - l == s1.length()) {
               return true;
            }
            char out = s2.charAt(l);
            l++;
            if (needMap.containsKey(out)) {
               winMap.put(out, winMap.getOrDefault(out, 0) - 1);
               if (winMap.get(out) < needMap.get(out)) {
                  validCount--;
               }
            }
         }
      }
      return false;
    }
}

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

leetcode第438题

解题思路

套用滑动窗口模板。窗口左右指针下标从0开始去遍历s。

窗口的右指针右移后,判断加入窗口的字符是否是p的字符,若是则更新winMap。更新后若winMap中该字符的value=needMap中该字符的value,说明滑动窗口中该字符数量与p中的该字符的数量相等,则validCount+1。

当validCount=needMap.size()时,说明p中的字符全部都包含在了滑动窗口中。此时进行判断,当窗口的长度=s的长度时,说明是一个合法序列,则加入列表中。

重复上述步骤,找出所有的合法序列。

复杂度分析

时间复杂度:O(nlogz + mlogz),n是s字符串的长度,m是p字串长度。最坏情况下,窗口右指针会扫描一遍s,窗口左指针会扫描一遍s,所以最多扫描2n次,而每扫描一次,就用若干次的map.get与map.put,则复杂度是nlogz。初始化needMap时,需要扫描一遍p,每次扫描也有map.get与map.put。则复杂度为O(nlogz + mlogz)。

空间复杂度:O(z)。z是字符集的大小。因为需要建立两个map分别存滑动窗口与字串中字符的出现次数,且每个map的键值对最多不会存放超过字符集大小。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
      Map<Character, Integer> needMap = new HashMap<>();
      for (int i = 0; i < p.length(); i++) {
         Character k = p.charAt(i);
         needMap.put(k, needMap.getOrDefault(k, 0) + 1);
      }
      Map<Character, Integer> winMap = new HashMap<>();
      List<Integer> list = new ArrayList<>();
      int l = 0, r = 0, validCount = 0;
      while (r < s.length()) {
         char in = s.charAt(r);
         r++;
         if (needMap.containsKey(in)) {
            winMap.put(in, winMap.getOrDefault(in, 0) + 1);
            if (winMap.get(in).equals(needMap.get(in))) {
               validCount++;
            }
         }
         while (validCount == needMap.size()) {
            if (r - l == p.length()) {
               list.add(l);
            }
            char out = s.charAt(l);
            l++;
            if (needMap.containsKey(out)) {
               winMap.put(out, winMap.get(out) - 1);
               if (winMap.get(out) < needMap.get(out)) {
                  validCount--;
               }
            }
         }
      }
      return list;
    }
}

无重复字符的最长子串

leetcode第3题

解题思路

此题不能用常规的滑动窗口模板。由于没有子串,所以不需要needMap去统计子串的字符,也不需要validCount统计窗口内满足子串相关条件的字符数。

窗口左右指针下标从0开始去遍历s。窗口的右指针右移后,将加入窗口的字符更新进winMap。

当winMap中刚加入窗口的字符的value大于1,则说明窗口中有重复的字符了。开始右移左指针,并实时更新winMap,直到winMap中刚加入窗口的字符的value不大于1。此时窗口长度就是一个无重复的子串长度。

重复上述步骤,找出最大子串长度。

复杂度分析

时间复杂度:O(nlogz),n 是s字符串的长度。最坏情况下,窗口右指针会扫描一遍s,窗口左指针会扫描一遍s,所以最多扫描2n次。而每扫描一次,就用若干次的map.get与map.put,则复杂度为O(nlogz)。

空间复杂度:O(z)。z是字符集的大小。因为需要建立一个map存滑动窗口中字符的出现次数,且map的键值对最多不会存放超过z是字符集的大小。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> winMap = new HashMap<>();
        int l = 0, r = 0, max = Integer.MIN_VALUE;
        while (r < s.length()) {
            char in = s.charAt(r);
            r++;
            winMap.put(in, winMap.getOrDefault(in, 0) + 1);
            while (winMap.get(in) > 1) {
                char out = s.charAt(l);
                l++;
                winMap.put(out, winMap.get(out) - 1);
            }
            max = Math.max(r - l, max);
        }
        return max == Integer.MIN_VALUE ? 0 : max;
    }
}

结尾

滑动窗口套路固定,遇到类型题时,直接模板默写代码,屡试不爽。 下篇文章讲二分搜索。

感谢各位人才的点赞、收藏和评论,干货文章持续更新中,下篇文章再见!

分类:

后端

标签:

数据结构与算法

作者介绍

xicheng
V1