文章摘要
Deepseek-v3.2

C++ GESP 五级：滑动窗口算法详解与例题

什么是滑动窗口算法？

滑动窗口算法是一种用于处理数组/字符串子区间问题的高效技巧。它通过维护一个窗口（通常是连续的子数组/子字符串），在遍历数据时滑动这个窗口来解决问题，避免重复计算。

滑动窗口算法的基本思想

  1. 使用两个指针（left 和 right）表示窗口的左右边界
  2. 右指针向右移动扩展窗口
  3. 当窗口不满足条件时，左指针向右移动收缩窗口
  4. 在窗口滑动过程中记录需要的结果

经典例题与代码实现

例题1：无重复字符的最长子串

问题描述：给定一个字符串，找出其中不含有重复字符的最长子串的长度。

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    if (n == 0) return 0;
    
    unordered_set<char> window;  // 用于记录窗口中的字符
    int left = 0, right = 0;     // 窗口的左右指针
    int maxLength = 0;           // 记录最大长度
    
    while (right < n) {
        // 如果当前字符不在窗口中，加入窗口并更新最大长度
        if (window.find(s[right]) == window.end()) {
            window.insert(s[right]);
            maxLength = max(maxLength, right - left + 1);
            right++;  // 右指针右移
        } else {
            // 如果字符已存在，左指针右移直到移除重复字符
            window.erase(s[left]);
            left++;
        }
    }
    
    return maxLength;
}

int main() {
    string s = "abcabcbb";
    cout << "输入: " << s << endl;
    cout << "无重复字符的最长子串长度: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

例题2：长度最小的子数组

问题描述：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = 0;     // 窗口左右指针
    int sum = 0;                 // 窗口内元素的和
    int minLength = INT_MAX;     // 最小长度
    
    while (right < n) {
        sum += nums[right];      // 扩展窗口
        right++;
        
        // 当窗口和满足条件时，尝试收缩窗口
        while (sum >= target) {
            minLength = min(minLength, right - left);
            sum -= nums[left];   // 收缩窗口
            left++;
        }
    }
    
    return minLength == INT_MAX ? 0 : minLength;
}

int main() {
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << "数组: ";
    for (int num : nums) cout << num << " ";
    cout << "\n目标值: " << target << endl;
    cout << "长度最小的子数组长度: " << minSubArrayLen(target, nums) << endl;
    return 0;
}

例题3：字符串的排列

问题描述：给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的排列。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool checkInclusion(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    if (len1 > len2) return false;
    
    vector<int> count1(26, 0);  // s1的字符频率
    vector<int> count2(26, 0);  // 窗口的字符频率
    
    // 初始化频率数组
    for (int i = 0; i < len1; i++) {
        count1[s1[i] - 'a']++;
        count2[s2[i] - 'a']++;
    }
    
    // 检查初始窗口
    if (count1 == count2) return true;
    
    // 滑动窗口
    for (int i = len1; i < len2; i++) {
        count2[s2[i] - 'a']++;           // 新字符加入窗口
        count2[s2[i - len1] - 'a']--;    // 旧字符移出窗口
        
        if (count1 == count2) return true;
    }
    
    return false;
}

int main() {
    string s1 = "ab", s2 = "eidbaooo";
    cout << "s1: " << s1 << ", s2: " << s2 << endl;
    cout << "s2是否包含s1的排列: " << (checkInclusion(s1, s2) ? "是" : "否") << endl;
    return 0;
}

例题4：最大连续1的个数 III

问题描述：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0，则返回数组中连续 1 的最大个数。

#include <iostream>
#include <vector>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int left = 0, right = 0;     // 窗口左右指针
    int zeroCount = 0;           // 窗口中0的个数
    int maxLength = 0;           // 最大长度
    
    while (right < nums.size()) {
        // 如果当前是0，增加0的计数
        if (nums[right] == 0) {
            zeroCount++;
        }
        
        // 如果0的个数超过k，收缩窗口
        while (zeroCount > k) {
            if (nums[left] == 0) {
                zeroCount--;
            }
            left++;
        }
        
        // 更新最大长度
        maxLength = max(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

int main() {
    vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
    int k = 2;
    cout << "数组: ";
    for (int num : nums) cout << num << " ";
    cout << "\nk = " << k << endl;
    cout << "最大连续1的个数: " << longestOnes(nums, k) << endl;
    return 0;
}

滑动窗口算法的模板

// 滑动窗口通用模板
int slidingWindowTemplate(vector<int>& nums, int target) {
    int left = 0, right = 0;     // 窗口边界
    int windowSum = 0;           // 窗口内数据的统计值
    int result = 0;              // 结果
    
    while (right < nums.size()) {
        // 将nums[right]加入窗口，更新统计值
        windowSum += nums[right];
        right++;
        
        // 判断窗口是否需要收缩
        while (windowSum > target) {  // 根据具体条件调整
            // 将nums[left]移出窗口，更新统计值
            windowSum -= nums[left];
            left++;
        }
        
        // 更新结果（根据具体问题调整位置）
        result = max(result, right - left);
    }
    
    return result;
}

滑动窗口算法的适用场景

  1. 子数组/子字符串问题：需要找到满足特定条件的连续子序列
  2. 最大/最小值问题：在满足约束条件下求最大或最小值
  3. 频率统计问题：涉及字符或数字频率的统计
  4. 优化时间复杂度：将O(n²)的暴力解法优化为O(n)

注意事项

  1. 窗口的移动条件：明确什么时候扩展窗口，什么时候收缩窗口
  2. 边界处理：注意数组越界问题
  3. 初始条件：合理初始化窗口和统计变量
  4. 结果更新时机：在适当的位置更新最终结果

通过掌握滑动窗口算法，你可以高效解决许多数组和字符串相关的复杂问题！