滑动窗口算法核心原理与经典例题解析
1. 长度最小的子数组
C++算法
滑动窗口算法核心原理与经典例题解析
滑动窗口算法利用双指针维护动态区间，适用于连续子数组或字符串问题。涵盖最小长度子数组和无重复字符最长子串两个经典案例。通过扩展右指针收缩左指针，将时间复杂度优化至 O(n)。代码实现采用 C++，包含哈希表优化方案，适合面试准备与算法基础巩固。
滑动窗口算法利用双指针维护动态区间，适用于连续子数组或字符串问题。涵盖最小长度子数组和无重复字符最长子串两个经典案例。通过扩展右指针收缩左指针，将时间复杂度优化至 O(n)。代码实现采用 C++，包含哈希表优化方案，适合面试准备与算法基础巩固。
遍历右指针：扩展窗口，从右边进窗口。判断：如果 sum >= target，更新最小长度，收缩窗口，从左边出窗口。
| 步骤 | left | right | 窗口 | sum | result |
|---|---|---|---|---|---|
| 4 | 0 | 3 | [2,3,1,2] | 8 | 4 |
| 7 | 2 | 4 | [1,2,4] | 7 | 3 |
| 10 | 4 | 5 | [4,3] | 7 | 2 |
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX;
int n = nums.size();
int sum = 0;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right]; // 进窗口
while (sum >= target) { // 判断
len = min(len, right - left + 1);
sum -= nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 集合 | O(n) | O(min(n, 128)) |
| 哈希表 | O(n) | O(min(n, 128)) |
| 数组（推荐） | O(n) | O(1) |
滑动窗口法：
遇到重复字符时，左指针直接跳到重复字符的下一个位置
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};
int ret = 0;
int n = s.size();
for (int left = 0, right = 0; right < n; right++) {
hash[s[right]]++; // 进窗口
while (hash[s[right]] > 1) { // 判断
hash[s[left++]]--; // 出窗口
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online