力扣 Hot100 滑动窗口算法解析（C++）

这个方法很直观，但效率太低。外层循环遍历每个起始位置，内层循环从起始位置向右延伸检查重复。对于长度为 n 的字符串，最坏情况下要检查 n²/2 个子串，时间复杂度是 O(n²)。当字符串很长时，这个算法会超时。

1.3 优化思路：滑动窗口

注意到暴力解法中有很多重复计算：比如检查从 i 到 j 的子串没有重复后，检查从 i 到 j+1 的子串时，其实只需要判断 s[j+1] 这个字符是否在前面出现过，不需要重新检查整个子串。

如果用滑动窗口的方法，维护一个窗口，窗口里的字符都是不重复的。右指针不断向右扩展窗口，当遇到重复字符时，左指针向右移动直到窗口内没有重复字符。

int lengthOfLongestSubstring(string s) { 
    unordered_map<char, int> charIndex; // 记录每个字符最近出现的位置 
    int n = s.size(); 
    int maxlength = 0; 
    int left = 0; // 窗口左边界 
    for(int right = 0; right < n; right++) { // 如果当前字符已存在且在窗口内 
        if(charIndex.count(s[right]) && charIndex[s[right]] >= left) { 
            left = charIndex[s[right]] + 1; // 左边界跳到重复字符的下一位 
        } 
        charIndex[s[right]] = right; // 更新字符位置 
        maxlength = max(maxlength, right - left + 1); // 更新最大长度 
    } 
    return maxlength; 
}

这个算法的关键是用哈希表记录每个字符最近出现的位置。右指针一直向右移动，左指针只有遇到重复字符时才移动。这样每个字符最多被访问两次（右指针一次，左指针一次），时间复杂度降到 O(n)。

这里有个细节要注意：判断字符是否在窗口内时，不仅要看这个字符是否出现过，还要看它最近出现的位置是否在 left 的右边。因为字符可能在窗口外面出现过，这种重复不影响当前窗口。

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

（s 和 p 只包含小写字母）

2.1 题目解析

这道题要在字符串 s 中找到所有是 p 的异位词的子串，返回这些子串的起始索引。异位词指的是字母相同但顺序可以不同的词，比如"abc"和"bca"是异位词。

2.2 初始思路

看到这道题，觉得很适合用滑动窗口，因为要找的是固定长度的子串。窗口长度就是 p 的长度，我们需要检查每个这个长度的窗口是否是 p 的异位词。

class Solution { 
public: 
    vector<int> findAnagrams(string s, string p) { 
        vector<int> result; 
        if(s.length() < p.length()) return result; // s 比 p 短，不可能有异位词 
        // 记录 p 中每个字符的出现次数 
        vector<int> pCount(26, 0); 
        for(char c : p) { 
            pCount[c - 'a']++; 
        } 
        // 记录窗口内字符的出现次数 
        vector<int> windowCount(26, 0); 
        int windowSize = p.length(); // 初始化第一个窗口 
        for(int i = 0; i < windowSize; i++) { 
            windowCount[s[i] - 'a']++; 
        } 
        // 检查第一个窗口 
        if(windowCount == pCount) { 
            result.push_back(0); 
        } 
        // 滑动窗口 
        for(int i = windowSize; i < s.length(); i++) { 
            // 移除窗口左边字符 
            windowCount[s[i - windowSize] - 'a']--; 
            // 添加窗口右边新字符 
            windowCount[s[i] - 'a']++; 
            // 检查当前窗口是否是异位词 
            if(windowCount == pCount) { 
                result.push_back(i - windowSize + 1); 
            } 
        } 
        return result; 
    } 
};

这个方法维护一个固定长度的窗口，每次滑动时更新窗口内字符计数，然后比较窗口计数和 p 的计数是否相同。时间复杂度是 O(n)，空间复杂度是 O(1)（因为只有 26 个小写字母）。

2.3 进一步优化

上面的方法需要每次都比较两个 26 位的数组，虽然常数时间，但还可以优化。可以用一个变量记录窗口和 p 的差异程度。

vector<int> findAnagrams(string s, string p) { 
    vector<int> result; 
    int sLen = s.length(), pLen = p.length(); 
    if(sLen < pLen) return result; 
    vector<int> count(26, 0); // 初始化：p 中的字符加 1，窗口中的字符减 1 
    // 这样如果 count 中某个字符为 0，表示这个字符在 p 和窗口中数量相同 
    for(int i = 0; i < pLen; i++) { 
        count[p[i] - 'a']++; 
        count[s[i] - 'a']--; 
    } 
    int diff = 0; // 记录有多少个字符的数量不匹配 
    for(int num : count) { 
        if(num != 0) diff++; 
    } 
    if(diff == 0) result.push_back(0); // 滑动窗口 
    for(int i = pLen; i < sLen; i++) { 
        char leftChar = s[i - pLen] - 'a'; 
        char rightChar = s[i] - 'a'; 
        // 移除左边字符 
        if(count[leftChar] == 0) diff++; // 原来匹配，现在移除后不匹配了 
        count[leftChar]++; 
        if(count[leftChar] == 0) diff--; // 现在又匹配了 
        // 添加右边字符 
        if(count[rightChar] == 0) diff++; // 原来匹配，现在添加后不匹配了 
        count[rightChar]--; 
        if(count[rightChar] == 0) diff--; // 现在又匹配了 
        if(diff == 0) result.push_back(i - pLen + 1); 
    } 
    return result; 
}

这个优化的好处是不用每次比较两个数组，只需要维护一个 diff 变量，表示有多少个字符在窗口和 p 中数量不同。当 diff 为 0 时，窗口就是 p 的异位词。每次窗口滑动时，只需要更新移出字符和移入字符对 diff 的影响。

3. 算法特点总结

滑动窗口算法特别适合处理连续子串或子数组问题。它的核心思想是维护一个窗口，通过移动窗口的左右边界来遍历所有可能的子串/子数组，同时高效地更新窗口状态。

3.1 窗口的三种类型

• 固定长度窗口：像第二题，窗口长度固定为 p 的长度，每次滑动一个位置检查
• 可变长度窗口：像第一题，窗口长度根据条件变化，右指针扩展窗口，左指针在条件不满足时收缩窗口
• 多指针窗口：有些复杂问题可能需要多个指针协同工作

3.2 滑动窗口的优点

• 通常能将 O(n²) 的暴力解法优化到 O(n)
• 思路清晰，代码结构统一
• 适合处理连续区间问题