微弱的光
0%

滑动窗口专项训练

发表于 更新于 6.1k 6 分钟

滑动窗口专项训练

更新记录

2024.5.17 第一次记录

一般解题步骤

待更新

1.定义需要维护的变量

可能是：

  • 哈希表（map或set）
  • 最短/最长长度

2.初始化滑动窗口，start和end一般都初始化为0（如果是双指针两边夹的情况，一般都是贪心？）

解题模板

由于自己的理解还不够深刻，这里借鉴大佬的思路

https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/solutions/879777/hua-dong-chuang-kou-zhen-di-jian-dan-yi-73bii

大佬的是python的版本

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
class Solution:
    def problemName(self, s: str) -> int:
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        x, y = ..., ...

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            x = new_x
            if condition:
                y = new_y

            '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否超过限定长度 
            # 如果超过了，窗口左指针前移一个单位保证窗口长度固定, 在那之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度大于限定值:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证窗口长度固定

            # Step 4 - 情况2
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法

        # Step 5: 返回答案
        return ...

按照大佬是思路，改成JS的版本

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
34
35
/**
 * @param {string} s
 */
var problemName = function(s) {
    // Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
	let [x, y] = ...
  
  // Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
    let st = 0;
  	for(let end = 0; end < s.length; s++){
        //Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
        x = new_x;
      	if(condition){
          y = new_y;
        }
      // Step 4 - 情况1
            // 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否超过限定长度 
            // 如果超过了，窗口左指针前移一个单位保证窗口长度固定, 在那之前, 先更新Step 1定义的(部分或所有)维护变量 
            if(窗口长度大于限定值){
               // 更新 (部分或所有) 维护变量 
                // 窗口左指针前移一个单位保证窗口长度固定
            }
              
            // Step 4 - 情况2
            // 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            // 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            // 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while(不合法){
            	//更新 (部分或所有) 维护变量 
              //不断移动窗口左指针直到窗口再次合法
            }           
    }
  // Step 5: 返回答案
  return ...
};

实战训练

无重复字符的最长子串

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

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

示例 1:

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

示例 2:

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

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

code:

不用map，用set和单纯数组都行，数组的话就用include方法来查看字母是否已经存在于数组中，但是最好还是不要数组了，数组里面删除一个元素会很麻烦，主要还是哈希+滑动窗口的思想。

用set的话会简单一点点

带注释版本

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
34
35
36
37
38
39
40
41
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    //无重复字符的最长子串
    //ex
    // abcabcbb
    // abc -> maxLen = 3
    //滑动窗口
    //1.定义需要维护的变量
    let maxLen = -1;
    let hash = new Map();
    //2.定义窗口的首尾端，然后滑动窗口
    let st = 0;
    for(let end = 0; end < s.length; end++){//第一次debug是end++写成s++了
        //维护变量
        let c = s[end];
        
        //情况2:窗口可变,检查窗口是否合法，不合法就调整st指针直至合法  
        //在该题目中，不合法指的是，字符串中出现重复字符 
        if(hash.has(c)){//c字符不是第一次出现，窗口不合法
            //只要连续移动字符，直到新的窗口的字符中不包含第一次出现的c字符位置
            while( st < end && s[st] != c){
                hash.delete(s[st]);//第二次debug，这一句和下面一句的顺序反了，如果先++在delet，那么相当于delet的是下一个字符，第一个字符永远都不会被移除
                st++;
            } 
            //此时的st应该位于第一个窗口的第一个c字符处
            st++;
            //现在窗口合法了
        }else{//第一次出现
            hash.set(c, 1);
        }

        //窗口的长度为end - st + 1 （左闭右闭区间）
        //如果是左闭右开区间，就是end - st
        maxLen = Math.max(maxLen, end - st + 1);
    }
    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
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    let maxLen = -1;
    let hash = new Map();
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];    
        if(hash.has(c)){
            while( st < end && s[st] != c){
                hash.delete(s[st]);
                st++;
            } 
            st++;
        }else{
            hash.set(c, 1);
        }
        maxLen = Math.max(maxLen, end - st + 1);
    }
    return maxLen;
};

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

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

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

Code:

窗口不合理的情况比较复杂

带注释版本

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    //哈希(异位词)+滑动窗口(子串)
    //异位词的特点是：
    //1.长度相等
    //2.每个字符的出现次数相等
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    //初始化hash
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    //初始化窗口，并开始滑动
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);

        //窗口不合法1，没有这个字符,两个指针都跳到这个指针后面
        if(!hash.has(c)){
            while(st != end + 1){//debug1,一开始没有跳转到st = end+1，只是st++，这样是不对的，而且跳转完之后，一定要记得移除hash2中前面的（已经不在滑动窗口中的）字母
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            //窗口不合法2,有这个字符，但是字符数多了,移动st，直到窗口中的c的字符数与hash中的字符数一致
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        //窗口不合法3，窗口长度超过了
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);//debug2，滑动了窗口，但是忘记处理hash2了
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};

不带注释版本

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
34
35
36
37
38
39
40
41
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);
        if(!hash.has(c)){
            while(st != end + 1){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};
-------------本文结束感谢您的阅读-------------
原创技术分享，您的支持将鼓励我继续创作