算法通关村第十六关白银挑战——滑动窗口高频问题

关注微信公众号：怒码少年。回复关键词【电子书】，领取多本计算机相关电子书
公众号后台开启了咨询业务，欢迎大家向我提问，免费，为爱发电😎

大家好，我是怒码少年小码。

武汉今天真的超级冷，骑车去上课真的是折磨啊啊啊啊！书接上回，我们来看看滑动窗口思想的几道经典算法题吧。

什么是算法中的滑动窗口思想

关于什么是滑动窗口思想，大家可以看我的上一篇文章：滑动窗口原来如此简单！

最长字串专题

无重复字符的最长子串

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

示例 1:

• 输入: s = “abcabcbb”
• 输出: 3
• 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

• 输入: s = “bbbbb”
• 输出: 1
• 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

分析：可以利用两个指针记录最长字串的首尾——窗口，尾指针如果遇到重复的元素就移动首指针到这个位置上重新开始记录。难点：如何记录已经遍历过的字符？答：map。

我们定义一个K-V形式的map，key表示的是当前正在访问的字符串，value是其下标索引值。我们每访问一个新元素，都将其下标更新成对应的索引值。具体过程如下图：

代码：

 public int lengthOfLongestSubstring(String s) {
    if(s.length() == 0) return 0;
    HashMap<Character,Integer> map = new HashMap<Character,Integer>();
    int max = 0 ; 
    int left = 0;
    for(int right = 0;right < s.length();right++){
      //如果map中已经含有right位置上的字符的key，就更新left的位置
      if(map.containsKey(s.charAt(right))){
          left = Math.max(left,map.get(s.charAt(right)) + 1);
      }
      //如果map中没有right位置上的字符，就把这个字符和他的下标加入map
      map.put(s.charAt(right),right);
      //计算left和right之间的元素个数，也就是最长字串
      max = Math.max(max,right - left + 1);
     }
   return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

至多包含两个不同字符的最长子串

LeetCode 159：给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。

示例：

• 输入: “eceba”
• 输出: 3
• 解释: t 是 “ece”，长度为3。

仍然使用left和right来锁定一个窗口，然后一边向右移动一边分析。我们用一个序列来看一下：aabbcccd。

可以得出需要解决两个问题，一个是怎么判断只有2个元素，另一个是移除的时候怎么知道移除谁，以及移除之后left是什么。

要判断只有2个元素，还是Hash好用，每一个时刻，这个 hashmap 包括不超过 3 个元素。这里还要考虑到要移除谁，所以我们要设计一下Hash的Key-Value的含义。我们把字符串里的字符都当做键，在窗口中的最右边的字符位置作为值。

public  int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 3) {
            return s.length();
        }
        int left = 0, right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int maxLen = 2;

        while (right < s.length()) {

            if (hashmap.size() < 3)
                hashmap.put(s.charAt(right), right++);

            // 如果大小达到了3个
            if (hashmap.size() == 3) {
                // 最左侧要删除的位置
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }

            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

至多包含k个不同字符的最长字串

LeetCode 340：给定一个字符串，找出至多包含k个不同字符的最长字串T。

怎么样？这题是不是很熟悉？其实就是相当于上一题升级了一下，所谓一通百通。

示例：

• 输入: s=“eceba”，k=2
• 输出: 3
• 解释: T 是 “ece”，长度为3。

代码上只要把hash判断的大小2改为k，超过k+1就可以了。

public  int lengthOfLongestSubstringTwoDistinct(String s,int k) {
        if (s.length() < k+1) {
            return s.length();
        }
        int left = 0, right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int maxLen = k;

        while (right < s.length()) {

            if (hashmap.size() < k+1)
                hashmap.put(s.charAt(right), right++);

            // 如果大小达到了k+1个
            if (hashmap.size() == k+1) {
                // 最左侧要删除的位置
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

长度最小的子数组

LeetCode 219：给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

• 输入：target=7，nums=[2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

分析：首先，用两个指针left和right记录字串，left和right都初始为零，right++一直往前走，直到left和right之间的和大于等于target，因为是要求和大于等于target的最小长度，所以此时要在和中减掉最左边的元素值直到它不符合和大于等于target的条件。

这也可以叫队列法，基本思路是先让元素不断入队，当入队元素和等于target时就记录一下此时队列的容量，如果队列元素之和大于target则开始出队， 直到小于target则再入队。

如果出现等于targe的情况，则记录一下此时队列的大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。

public int minSubArrayLen(int target, int[] nums) {
    int left = 0,right = 0,sum = 0,min=Integer.MAX_VALUE;
    while(right < nums.length){
        sum += nums[right++];
        while(sum >= target){
            min = Math.min(min,right - left);
            sum -= nums[left++];
        }
    }
    return min == Integer.MAX_VALUE ? 0:min;
}
1
2
3
4
5
6
7
8
9
10
11

盛水最多的容器

LeetCode 11：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

**注意：**你不能倾斜容器喔~

分析：这里的关键就是找到求容器面积的公式，然后在求出最大值。

思路：本题看似复杂，但其实简单的很。设两指针 i , j，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的短板决定，因此可得如下面积公式 ：

S(i,j)=min(h[i],h[j])×(j−i)

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度−1 变短：

• 若向内移动短板 ，水槽的短板min(h[i],h[j])可能变大，因此下个水槽的面积可能增大 。
• 若向内移动长板 ，水槽的短板min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小 。

因此，这里的一个关键点是要找到短板，也就是需要把h[i] , h[j]进行比较。只要初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出。

public int maxArea(int[] height) {
    int i=0,j = height.length - 1,res = 0;
    while(i < j){
        if(height[i] < height[j]){
            res = Math.max(res,(j-i)*height[i++]);
        }else{
            res = Math.max(res,(j-i)*height[j--]);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11

寻找子串异位词

两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。如何判断两个字符串是否互为排列，是字符串的一个基本算法。

字符串的排列

LeetCode 567：给你两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。如果是返回true；否则，返回false。（换句话说，s1的排列之一是s2的子串。

示例 1：

• 输入：s1 = “ab” s2 = “eidbaooo”
• 输出：true
• 解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：

• 输入：s1= “ab” s2 = “eidboaoo”
• 输出：false

本题因为字符串s1的异位词长度一定是和s2字符串的长度一样的，所以很自然的想到可以以s1.length()为大小截图一个固定窗口，然后窗口一边向右移动，一边比较就行了。

public boolean checkInclusion(String s1, String s2) {
    int sLen1 = s1.length(), sLen2 = s2.length();
    // 检查s1的长度是否大于s2，如果是，则s2不可能包含s1，直接返回false
    if (sLen1 > sLen2) {
        return false;
    }

    int[] charArray1 = new int[26]; // s1字符串中每个字符出现次数的计数器
    int[] charArray2 = new int[26]; // s2字符串中每个字符出现次数的计数器

    // 分别计算s1和s2的前s1.length()字符中每个字符出现的次数
    for (int i = 0; i < sLen1; ++i) {
        ++charArray1[s1.charAt(i) - 'a']; // 对应字符的计数器加一
        ++charArray2[s2.charAt(i) - 'a'];
    }

    // 比较两个计数器数组是否相等
    if (Arrays.equals(charArray1, charArray2)) {
        return true; // 如果相等，则s1包含在s2的左边部分
    }

    // 依次向右滑动窗口，更新charArray2的值，比较两个计数器数组是否相等
    for (int right = sLen1; right < sLen2; ++right) {
        ++charArray2[s2.charAt(right) - 'a']; // 新进入窗口的字符增加计数器
        int left = right - sLen1; // 左移滑动窗口的索引
        --charArray2[s2.charAt(left) - 'a']; // 离开窗口的字符减少计数器
        if (Arrays.equals(charArray1, charArray2)) {
            return true; // 如果相等，则s1包含在s2的某个中间部分
        }
    }

    return false; // s2不包含s1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

该方法使用滑动窗口的思想来判断字符串s2是否包含s1。具体步骤如下：

1. 首先，判断s1的长度是否大于s2的长度，如果是，则s2不可能包含s1，直接返回false。
2. 声明两个整数数组charArray1和charArray2，分别用于统计s1和前s1.length()个字符在两个字符串中出现的次数。初始时，两个数组中的所有元素都为0。
3. 使用循环遍历s1的前s1.length()个字符，并更新charArray1和charArray2中相应字符的计数器。
4. 对比charArray1和charArray2数组，如果两者相等，则表示s1包含在s2的左边部分，直接返回true，否则继续执行。
5. 使用一个滑动窗口，从s1.length()开始遍历s2的字符。
6. 每次滑动窗口向右滑动一位，更新charArray2中新进入窗口的字符的计数器，同时减少离开窗口的字符的计数器。
7. 对比charArray1和charArray2数组，如果两者相等，则表示s1包含在s2的某个中间部分，直接返回true。
8. 如果遍历完整个s2字符串后，仍然没有找到包含s1的情况，则返回false。

++charArray1[s1.charAt(i) - 'a'];是用于增加charArray1数组中相应字符的计数器。s1.charAt(i)是用于获取字符串s1中索引为i的字符。'a'是字符常量，表示字母a。

s1.charAt(i) - 'a'的作用是将s1中索引为i的字符转换为相对于字母a的偏移量，例如偏移量为0表示字符为a，偏移量为1表示字符为b，以此类推。

charArray1[s1.charAt(i) - 'a']表示对应字符的计数器在数组charArray1中的位置。最后，++操作符对计数器进行自增操作。

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

LeetCode 438:给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

• 输入: s = “cbaebabacd”, p = “abc”
• 输出: [0,6]
• 解释:
  起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
  起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

本题的思路和实现与上面几乎一模一样，唯一不同的是需要用一个List，如果出现异位词，还要记录其开始位置，那直接将其add到list中就可以了。完整代码：

public List<Integer> findAnagrams(String s, String p) {
  int sLen = s.length(),pLen = p.length();
  if(sLen < pLen){
      return new ArrayList<Integer>();
  }
  List<Integer> ans = new ArrayList<Integer>();
  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)){
      ans.add(0);
  }
  for(int left = 0;left < sLen - pLen;++left){
      --sCount[s.charAt(left) - 'a'];
      int right = left + pLen;
      ++sCount[s.charAt(right) - 'a'];
      if(Arrays.equals(sCount,pCount)){
          //上面的left多减了一次，所以
          ans.add(left + 1);
      }
  }
  return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

END

这一篇可以说是把经典的滑动窗口的题目都汇总了，但是我还是不是很懂，啊啊啊啊好烦啊啊啊啊，没办法，只能硬啃了。

持续关注的小伙伴可能发现我最近的更文速度变慢了，那是因为最近有实验和项目，但是大家放心，我是一定会更完的！持续关注，不要走开！！