当前位置：首页 > ds >正文

C/C++滑动窗口算法深度解析与实战指南

ds 2025/5/6 12:09:33

C/C++滑动窗口算法深度解析与实战指南

引言

滑动窗口算法是解决数组/字符串连续子序列问题的利器，通过动态调整窗口边界，将暴力解法的O(n²)时间复杂度优化至O(n)。本文将系统讲解滑动窗口的核心原理、C/C++实现技巧及经典应用场景，助您掌握这一高效算法。

一、算法核心原理

1.1 窗口双指针模型

左右指针：使用left和right指针界定窗口边界
动态调整：
- 扩展窗口：右指针右移扩大窗口范围
- 收缩窗口：当条件不满足时左指针右移缩小窗口
状态维护：通过哈希表/数组记录窗口内元素状态

1.2 两种窗口类型

窗口类型	特点	典型场景
固定窗口	窗口大小恒定	滑动平均值、固定长度子数组
可变窗口	窗口大小动态调整	最长无重复子串、最小覆盖子串

二、C/C++实现详解

2.1 固定窗口实现模板

int fixedWindow(vector<int>& nums, int k) {int sum = 0, max_sum = 0;// 初始化窗口for (int i = 0; i < k; ++i) sum += nums[i];max_sum = sum;// 滑动窗口for (int right = k; right < nums.size(); ++right) {sum += nums[right] - nums[right - k];  // 滚动更新max_sum = max(max_sum, sum);}return max_sum;
}

2.2 可变窗口实现模板

int variableWindow(string s) {unordered_map<char, int> window;int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];window[c]++;  // 扩展窗口// 收缩条件：出现重复字符while (window[c] > 1) {char d = s[left];window[d]--;  // 移出左边界left++;}max_len = max(max_len, right - left + 1);  // 更新结果}return max_len;
}

三、经典问题解析

3.1 无重复字符的最长子串（LeetCode 3）

int lengthOfLongestSubstring(string s) {vector<int> char_map(128, -1);  // ASCII映射表int max_len = 0, left = 0;for (int right = 0; right < s.size(); ++right) {if (char_map[s[right]] >= left) {left = char_map[s[right]] + 1;  // 跳跃收缩}char_map[s[right]] = right;  // 更新最新位置max_len = max(max_len, right - left + 1);}return max_len;
}

3.2 最小覆盖子串（LeetCode 76）

string minWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, valid = 0, start = 0, min_len = INT_MAX;for (int right = 0; right < s.size(); ++right) {char c = s[right];if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}// 收缩窗口while (valid == need.size()) {if (right - left + 1 < min_len) {min_len = right - left + 1;start = left;}char d = s[left++];if (need.count(d)) {if (window[d] == need[d]) valid--;window[d]--;}}}return min_len == INT_MAX ? "" : s.substr(start, min_len);
}