当前位置：首页 > article >正文

Leetcode 刷题记录 03 —— 滑动窗口

article 2025/3/15 0:02:03

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

01 无重复字符的最长子串

方法：滑动窗口

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

方法一：滑动窗口

方法二：滑动窗口Plus

01 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

方法：滑动窗口

建立左指针 lk 和右指针 rk
lk 指向滑动窗口第一个元素
rk 指向滑动窗口最后一个元素
不断地去掉第一个元素，添加最后一个元素，判断 !occ.count(s[rk+1])

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk = -1; //右指针
        int ans = 0;

        for(int lk=0; lk<n; ++lk){ //左指针
            if(lk != 0) occ.erase(s[lk-1]);
            while(rk+1 < n && !occ.count(s[rk+1])){
                occ.insert(s[rk+1]);
                ++rk;
            }
            ans = max(ans, rk-lk+1);
        }
        return ans;
    }
};

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

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        
    }
};

方法一：滑动窗口

建立两个数组 sCount(26) 和 pCount(26)
sCount(26) 记录 s 中的字母情况
pCount(26) 记录 p 中的字母情况
不断地去掉第一个元素，添加最后一个元素，判断 sCount == pCount

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();
        if(sLen < pLen) return vector<int>();

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for(int i=0; i<pLen; ++i){
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }
        if(sCount == pCount) ans.emplace_back(0);

        for(int i=0; i<(sLen - pLen); ++i){
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if(sCount == pCount) ans.emplace_back(i + 1);
        }
        return ans;
    }
};

方法二：滑动窗口Plus

建立一个数组 count(26)
count(26) 记录 s 和 p 差异情况
不断地去掉第一个元素，添加最后一个元素，判断 differ == 0

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();
        if(sLen < pLen) return vector<int>();

        vector<int> ans;
        vector<int> count(26);
        int differ = 0;

        for(int i=0; i<pLen; ++i){
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }
        for(int j=0; j<26; j++){
            if(count[j]) ++differ;
        }
        if(differ == 0) ans.emplace_back(0);

        for(int i=0; i<(sLen - pLen); ++i){
            if(count[s[i] - 'a'] == 0) ++differ;
            else if(count[s[i] - 'a'] == 1) --differ;
            --count[s[i] - 'a'];

            if(count[s[i + pLen] - 'a'] == 0) ++differ;
            else if(count[s[i + pLen] - 'a'] == -1) --differ;
            ++count[s[i + pLen] - 'a'];

            if(differ == 0) ans.emplace_back(i + 1);
        }
        return ans;
    }
};