LeetCode Hot 100：滑动窗口

LeetCode Hot 100：滑动窗口

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

思路 1：滑动窗口 + 哈希表

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLen = 0;
        unordered_set<char> hashSet;
        for (int left = 0, right = 0; right < n; right++) {
            while (hashSet.count(s[right])) {
                hashSet.erase(s[left]);
                left++;
            }
            hashSet.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

思路 2：动态规划 + 哈希表

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        unordered_map<char, int> dic;
        int res = 0, tmp = 0;
        for (int left, right = 0; right < n; right++) {
            if (dic.find(s[right]) == dic.end())
                left = -1;
            else
                left = dic.find(s[right])->second; // 获取索引 i
            // 更新哈希表
            dic[s[right]] = right;
            // dp[j - 1] -> dp[j]
            tmp = tmp < right - left ? tmp + 1 : right - left;
            res = max(res, tmp);
        }
        return res;
    }
};

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

思路 1：固定长度滑动窗口 + 哈希表

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

        vector<int> sCount(26, 0), pCount(26, 0);
        vector<int> ans;

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

        if (sCount == pCount)
            ans.push_back(0);

        for (int i = pLen; i < sLen; i++) {
            sCount[s[i - pLen] - 'a']--;
            sCount[s[i] - 'a']++;
            if (sCount == pCount)
            {
                // 子串开头是 i - pLen + 1
                ans.push_back(i - pLen + 1);
            }
        }
        return ans;
    }
};

思路 2：可变长度滑动窗口 + 哈希表

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

        vector<int> sCount(26, 0), pCount(26, 0);
        vector<int> ans;

        for (int i = 0; i < pLen; i++)
            pCount[p[i] - 'a']++;

        if (sCount == pCount)
            ans.push_back(0);

        for (int left = 0, right = 0; right < sLen; right++) {
            sCount[s[right] - 'a']++;
            while (sCount[s[right] - 'a'] > pCount[s[right] - 'a']) {
                sCount[s[left] - 'a']--;
                left++;
            }
            if (right - left + 1 == pLen)
                ans.push_back(left);
        }

        return ans;
    }
};