Grizzly's daily
0%

字符串解题技巧1——滑动窗口

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

本文是关于字符串的子串问题，就数据结构的形态来说还是属于数组的问题，这里主要是关于使用双指针解决滑动窗口的问题。

涉及 leetcode 的76. 最小覆盖子串、567. 字符串的排列、438. 找到字符串中所有字母异位词和3. 无重复字符的最长子串。

包含子串元素问题

76. 最小覆盖子串、567. 字符串的排列和438. 找到字符串中所有字母异位词这一系列的问题都是关于在字符串中包含子串元素的问题。

题目1

首先来看这些题目567. 字符串的排列：给你两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true；否则，返回 false。

换句话说，s1 的排列之一是 s2 的子串。

示例1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

示例2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

理解一下1

题目的大概意思就是：给你一个子串 s1，需要判断在 s2 中是否一个子串包含子串 s1 中的所有元素。

基本的思路是：

  1. 获得子串s1的长度Len；
  2. 按照Len的大小，使用左右索引指针组成的固定窗口，在字符串s2上滑动；
  3. 不断比较窗口内的子串和s1的元素是否相同；
  4. 比较的方法可以使用hash表或数组，比较各个元素出现的次数相同即可。

以上的方法需要的时间复杂度为两个字符串长度的乘积，即O(NM)。

想要优化到O(n)，则可以使用不固定的滑动窗口来完：

  1. 首先使用hash表记录子串s1中元素出现的次数；
  2. 初始化在s2上的左右索引指针为0；
  3. 右索引指针进行向右扩张，不断将字符纳入窗口；
  4. 判断新加入的字符是否子串s1中的，若是则在窗口hash表记录字符及其个数；
  5. 此时若窗口内的子串不满足子串s1的元素要求，那么左索引指针右移来缩小窗口范围，并更新相应内容即可。

解题1

以上的思路可能我没有很清楚的表示，不过没关系，我们弄清楚以下几点：

  1. 移动right扩大窗口时该做什么？：判断新纳入窗口的字符是否是我们需要的，若需要则加入，并增加字符个数valid；
  2. 何时停止扩大窗口，并移动left缩小窗口？：窗口大小 ≥ 子串大小时；
  3. 缩小窗口时该干什么？；
    • 首先判断此时是否已经满足条件，若满足则直接返回；
    • 否则移除left处元素，若是需要的元素，则更新有效值，并删除窗口内的元素。

还是看代码逻辑吧

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
bool checkInclusion(string s1, string s2) {
    // need是子串元素hash表，window是滑动窗口
    unordered_map<char, int> need, window;
    // 初始化need子串
    for(char c : s1)
        need[c]++;
    int left = 0, right = 0;  // 区间左闭右开
    int valid = 0;  // 窗口内有效元素个数
    while(right < s2.size()){
        char c = s2[right];  // 右移字符进入子串hash
        right++;
        if(need.count(c)){  // 1. 若是需要元素则修改hash
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }
        // 2. 区域可缩小
        while(right-left >= s1.size()){
            // 3.1 满足条件直接返回
            if(valid == need.size()){
                return true;
            }
            char d = s2[left];
            left++;
            // 3.2 移除元素
            if(need.count(d)){
                if(window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return false;
}

ok，有了以上的代码再看剩下两题几乎是一模一样，就不详细解说了，代码如下：

76. 最小覆盖子串

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
string minWindow(string s, string t) {
    // need是子串元素hash，window是滑动窗口
    unordered_map<char, int> need, window;
    // 初始化need子串
    for(char c : t)
        need[c]++;
    int left = 0, right = 0; // 区间左闭右开
    int valid = 0;  // 窗口内有效元素个数
    int start = 0, len = INT_MAX;  // 最终起点和长度
    while(right < s.size()){
        char c = s[right];  //右移字符进入子串hash
        right++;
        if(need.count(c)){  //若需要则修改hash
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }
        while(valid == need.size()){  //窗口内的元素已经满足需要
            if(right-left < len){  // 可以收缩窗口就更新结果
                start = left;
                len = right - left;
            }
            char d = s[left];
            left++;
            if(need.count(d)){
                if(window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

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

所谓异位词也就是子串重新排列嘛，不用感到新奇。

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
vector<int> findAnagrams(string s, string p) {
    unordered_map<char, int> need, window;
    for(char c : p)
        need[c]++;
    int left = 0, right = 0;
    int valid = 0;
    vector<int> res;
    while(right < s.size()){
        char c = s[right++];
        if(need.count(c)){
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }
        while(right-left >= p.size()){
            if(valid == need.size()){
                res.emplace_back(left);
            }
            char d = s[left++];
            if(need.count(d)){
                if(window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

无重复字符的最长子串

这题其实与以上三题大差不差，只不过这里没有给定子串，而是需要我们求出子串而已。

题目2

首先来看题目3. 无重复字符的最长子串：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例1：

输入："abcabcbb"

输出：3

示例2：

输入：s = "bbbbb"

输出：1

理解一下2

题目的大概意思就是：找出字符串中元素不重复的子串的长度，也就是需要子串中的元素不重复，个数要尽可能的多。

保持之前的解题思路，但是这里就不需要needhash表和valid值了，因为我们没有需要比较的子串，但是需要一个res来记录长度：

  1. 右侧子串向前扩张，将新字符纳入窗口；
  2. 判断该窗口内加入的该子串是否重复；
  3. 若重复，则左侧索引指针收缩，直至将重复元素抛出；
  4. 判断此时的长度与res大小，更新最大子串长度。

解题2

很简单吧，看代码更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int res = 0;
    while(right < s.size()){
        // 扩张
        char c = s[right++];
        window[c]++;
        // 有重复的字符
        while(window[c] > 1){
            // 收缩
            char d = s[left++];
            window[d]--;
        }
        res = max(res, right - left);
    }
    return res;
}

个人收获

之前使用双指针解决链表的时候，用快慢指针来解决一些链表上的逻辑问题；但是在字符串这种类似数组的数据结构中也是可以使用索引来表示指针，解决一些逻辑问题。

滑动窗口的结合hash表既可以来表示区域内的元素数量了，对于一些不要求顺序的子串问题就可以使用该方法解决。

------ 本文结束------