滑动窗口算法详解与实战案例

注意 hash 数组的大小需覆盖所有可能的 ASCII 码值，这里 129 足够容纳标准字符。

3. 最多 K 个零的最长连续 1

问题描述： 给定一个二进制数组和一个整数 k，允许将最多 k 个 0 翻转为 1，求翻转后最长的连续 1 的数量。

思路分析： 这是一个典型的'允许错误'类滑动窗口。我们用 zero 变量记录当前窗口内 0 的个数。如果 zero 超过 k，说明窗口非法，需要移动左指针缩小范围，直到 zero 回到合法范围内。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++) {
            if (nums[right] == 0) zero++;
            while (zero > k) {
                if (nums[left] == 0) zero--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

4. 减少到目标值的最小操作数

问题描述： 给定一个整数数组和一个整数 x，每次可以从数组两端移除一个元素，使得剩余元素的和等于 x - 移除元素的和。求最少操作次数。

思路分析： 直接求两端的和比较复杂。换个角度思考：如果我们移除了两端，剩下的就是中间的一段连续子数组。因此，问题转化为：寻找和为 sum(nums) - x 的最长连续子数组。这样就能复用标准的滑动窗口模板了。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        int ret = -1;
        int target = sum - x;
        
        // 特殊情况处理
        if (target < 0) return -1;
        
        // 转化为求中间连续数组的和的大小
        for (int left = 0, right = 0, temp = 0; right < nums.size(); right++) {
            temp += nums[right];
            while (temp > target) {
                temp -= nums[left++];
            }
            if (temp == target) {
                ret = max(ret, right - left + 1);
            }
        }
        
        if (ret == -1) return ret;
        else return n - ret;
    }
};

这种'转化思维'在算法题中非常关键，往往能化繁为简。

5. 水果成篮

问题描述： 你正在访问一家农场，只有一排果树。每种树结一种水果。你只能拿两种不同类型的水果，且必须连续采摘。求最多能摘多少水果。

思路分析： 这其实是'无重复字符的最长子串'的变种，只是限制类型数量变为 2。我们需要用哈希表记录每种水果的数量，当种类超过 2 时，收缩左边界。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0};
        int ret = 0;
        for (int left = 0, right = 0, kind = 0; right < fruits.size(); right++) {
            if (hash[fruits[right]] == 0) kind++;
            hash[fruits[right]]++;
            while (kind > 2) {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0) kind--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

6. 字符串中的字母异位词

问题描述： 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。

思路分析： 这是一个固定长度的滑动窗口。窗口大小始终等于 p 的长度。我们需要比较窗口内的字符频次是否与 p 完全一致。使用 count 变量来跟踪匹配成功的字符数，可以减少每次遍历整个窗口的开销。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
        for (auto ch : p) hash1[ch - 'a']++;
        
        int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
        int m = p.size();
        
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right]; // 进窗口 + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            
            if (right - left + 1 > m) { // 判断
                char out = s[left++];
                // 出窗口 + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            
            if (count == m) ret.push_back(left);
        }
        return ret;
    }
};

7. 连接所有单词的子串

问题描述： 给定一个字符串 s 和一些长度相同的单词 words，找出 s 中恰好由 words 中所有单词串联组成的子串的起始位置。

思路分析： 这道题稍微复杂一些，因为涉及单词级别的匹配。我们需要对每个可能的起始位置进行滑动，窗口大小固定为 words.size() * word.length()。利用哈希表统计单词频次，并在滑动过程中动态更新差异计数。

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word : words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

8. 最小覆盖子串

问题描述： 给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。

思路分析： 这是滑动窗口中最经典的'最小覆盖'问题。我们需要维护两个哈希表，分别记录目标字符需求量和当前窗口内的字符量。当窗口满足条件时，尝试收缩左边界以找到最小长度。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int kind = 0;
        for (auto e : t) {
            if (hash1[e] == 0) kind++;
            hash1[e]++;
        }
        
        int hash2[128] = {0};
        int minlen = INT_MAX, begin = -1;
        
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++;
            
            while (count == kind) {
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--;
            }
        }
        
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

通过以上八个案例，我们可以看到滑动窗口虽然形态各异，但核心逻辑始终是：扩张右边界以满足条件 -> 收缩左边界以优化结果。掌握这一模式，配合哈希表或计数器，就能解决绝大多数相关难题。