在字符串处理算法中，滑动窗口（Sliding Window）是非常高频的题型。它的核心思想是：

通过一个左右边界构成窗口，动态扩张或收缩以满足题目要求。

今天我们基于两道经典 LeetCode 题来深入理解滑动窗口的使用：

• LC3：无重复字符的最长子串

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

一、无重复字符的最长子串（LC3）

核心思路

• 维护一个窗口，保证内部 没有重复字符

• 每次向右扩展窗口

• 如果加入新字符后重复 → 左边收缩

• 用 unordered_map 记录字符出现次数

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 思路： 本质就是维护一个窗口，右边加入元素，当加入后窗口不满足条件后，左边就滑动来删除元素
        unordered_map<char, int> mp;
        int ans = 0;
        int left = 0;
        for (int right = 0; right < s.size(); ++right) {
            mp[s[right]]++;
            while(mp[s[right]] > 1) {       // 注意这里是while,因为一直要滑动到左边界重复的那个完全出去。
                mp[s[left]]--;         // 注意先给mp里的value--再移动left
                left++;
                
            }
            ans = max(ans, right - left + 1);
        } 
        return ans;
    }
};

时间 & 空间复杂度

复杂度	分析
时间复杂度 O(n)	每个指针最多移动 n 次
空间复杂度 O(1)	map大小最多 128（ASCII 字符）

---

技巧总结

• while 而不是 if，因为可能需要多次收缩

• right-left+1 是窗口长度

• 滑动窗口适合保持区间内无重复/满足唯一性约束

---

---

二、字母异位词查找（LC438）

核心思路

• 固定窗口大小 = p.length()

• 使用数组统计字符频次

• 每次滑动窗口比较两边频次数组

代码

class Solution {
    // 思路： 定窗口长度， 先算出p对应的字母出现次数，然后right往后走定窗滑动，一直到left>=0说明窗口合理，此时计算字母出现次数，和前面算出的p比较，符合就记录下答案
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int n = s.size();
        array<int, 26> cnt_p{};
        array<int, 26> cnt_s{};
        int window_len = p.size();
        if (n < window_len) {
            return ans;
        }
        for (int i = 0; i < window_len; ++i) {
            cnt_p[p[i] - 'a']++;
        }
        for (int right = 0; right < n; ++right) {
            int left = right - window_len + 1;
            cnt_s[s[right] - 'a']++;
            if (left >= 0) {
                if (cnt_p == cnt_s) {
                    ans.push_back(left);
                }
                cnt_s[s[left] - 'a']--;
            } 
        }
        return ans;
    }
};

时间 & 空间复杂度

复杂度	分析
时间复杂度 O(n)	right 每次移动一次，数组比较 O(26) 常数级
空间复杂度 O(1)	固定 26 字母统计

---

技巧总结

• 固定窗口大小的滑动窗口

• 使用 array<int,26> 比 map 更快

• 比较两个频次数组判断“异位词”

---

两题对比总结

题目	窗口大小	判断条件	数据结构
LC3 最长无重复子串	可变窗口	没有重复	哈希表（计数）
LC438 异位词查找	固定窗口	频率完全一致	字母计数数组

一句话区别👇

一个动态扩张窗口，一个固定大小窗口滑动。

---

滑动窗口模板总结

for (right ... ) {
    扩大窗口
    更新数据结构

    while(窗口不合法) {
        缩小窗口
        更新数据结构
    }

    根据题意更新答案
}

牢记三个动作：

扩 张	检 查	收 缩
right++	是否满足条件？	left++

---

滑动窗口适用场景

典型目标	示例题目
无重复/唯一性	最长无重复子串
固定窗口统计	异位词、平均数窗口
子数组满足条件的最优长度	最短子数组和、最优区间

字符串 + 最长子数组 + 条件约束 = 滑动窗口 80% 出场率

---

总结一句话

滑动窗口的本质就是：
右指针不断扩大搜索范围，左指针适时缩小范围以满足条件。