字符串：滑动窗口

睡不醒的鲤鱼 2021-10-02 每日一题 LeetCode

# 0003. 无重复字符的最长子串 (opens new window)

题目

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

示例 1:

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

1
2
3

示例 2:

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

1
2
3

示例 3:

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

1
2
3
4

提示：

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

解析

使用一个数组记录每个字符上次出现的位置，在遍历的同时移动窗口左边界，最后返回窗口长度的最大值即可。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> pos(128, -1);
        int ans = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            j = max(j, pos[s[i]] + 1);
            ans = max(ans, i - j + 1);
            pos[s[i]] = i;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# 0030. 串联所有单词的子串 (opens new window)

题目

给定一个字符串 s 和一些长度相同的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

解析

维护一个长度为 m 个单词的滑动窗口，保证窗口内的单词与完全匹配 words。

需要注意的是，words 内的单词长度相同，因此可以按照单词的长度来移动滑动窗口，最终通过一个额外的 cnt 变量来统计两个哈希表的匹配单词数即可。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if (words.empty()) return ans;

        int n = s.length(), m = words.size(), w = words[0].length();

        // 记录目标串每个单词应出现的次数
        unordered_map<string, int> total;
        for (int i = 0; i < words.size(); i++) {
            total[words[i]]++;
        }

        for (int i = 0; i < w; i++) {
            unordered_map<string, int> window;
            int cnt = 0;
            for (int j = i; j + w <= n; j += w) {
                // 超过目标串长度，需要去除头部的字符串
                if (j >= i + m * w) {
                    string word = s.substr(j - m * w, w);
                    window[word]--;
                    if (window[word] < total[word]) cnt--;
                }
                // 新增的字符串
                string word = s.substr(j, w);
                window[word]++;
                if (window[word] <= total[word]) cnt++;

                // 完全匹配，添加结果
                if (cnt == m) ans.push_back(j - (m - 1) * w);
            }
        }
        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
28
29
30
31
32
33
34
35
36

# 0076. 最小覆盖子串 (opens new window)

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

解析

使用双指针 i、j，其中 i 遍历字符串 s，j 用来寻找满足条件的位置，使得 j 到 i 的字符串刚好包含字符串 t 的所有字符。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for (int i = 0; i < t.length(); i++) ht[t[i]]++;

        string ans;
        for (int i = 0, j = 0, cnt = 0; i < s.length(); i++) {
            // 添加当前字符，更新有效字符数量
            if (++hs[s[i]] <= ht[s[i]]) cnt++;
            
            // j 向前移动，去除冗余字符
            while (j <= i && hs[s[j]] > ht[s[j]]) hs[s[j++]]--;

            // 完全覆盖，更新 ans
            if (cnt == t.length()) {
                if (ans.empty() || ans.length() > i - j + 1) {
                    ans = s.substr(j, i - j + 1);
                }
            }
        }
        return ans;
    }
};

代码

字符串：双指针字符串：异位词

鲤鱼笔记

Choose mode