LeetCode Hot100 SlideWindow

Posted on

无重复字符的最长子串

Problem

https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked

Solution

维护一个动态大小的滑动窗口，不断扩大有右边界，在出现重复字符时缩小左边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int l = 0;
        int ans = 0;
        unordered_set<char> chSet;
        for (int r = 0; r < n; r ++)
        {
            while (chSet.count(s[r]))
            {
                chSet.erase(s[l]);
                l ++;
            }
            chSet.insert(s[r]);
            ans = max(ans, r-l+1);
        }
        return ans;
    }
};

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

Problem

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

Solution

通过统计字符串中各个字符个数判断是否为字母异位词，维护一个和p的长度一样的滑动窗口。

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.length();
        int pLen = p.length();

        vector<int> pCount(26, 0);
        for (int i = 0; i < pLen; i ++)
        {
            pCount[p[i]-'a'] ++;
        }
        vector<int> ans;
        int l = 0;
        vector<int> sCount(26, 0);
        for (int r = 0; r < sLen; r ++)
        {
            sCount[s[r]-'a'] ++;

            if (r - l + 1 > pLen)
            {
                sCount[s[l]-'a'] --;
                l ++;
            }

            if (sCount == pCount)
            {
                ans.push_back(l);
            }
        }
        return ans;
    }
};