滑动窗口算法详解与实战案例
滑动窗口（Sliding Window）是处理数组或字符串连续子段问题的常用技巧。它的核心思想是利用两个指针维护一个动态区间，通过移动左右边界来寻找满足条件的最优解。相比暴力枚举，滑动窗口能将时间复杂度从 O(N^2) 优化至 O(N)，在处理'最长'、'最短'、'包含'等约束条件时尤为高效。
下面我们通过几个经典 LeetCode 题目，逐步拆解滑动窗口的不同变体和应用场景。
1. 最小长度子数组
问题描述： 给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。
思路分析： 最直观的做法是双重循环枚举所有子数组，但效率较低。我们可以使用滑动窗口：右指针不断扩展窗口以增大和，一旦和满足条件，左指针就开始收缩窗口以尝试找到更短的长度。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= s) {
ans = min(ans, j - i + 1);
break;
}
}
}
return ans == INT_MAX ? 0 : ans;
}
};
虽然上述代码展示了基础逻辑，但在实际工程中，我们通常会进一步优化为真正的双指针滑动窗口结构，避免重复计算。
2. 无重复字符的最长子串
问题描述： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
思路分析： 这里需要记录字符出现的次数。当右指针遇到重复字符时，左指针必须向右移动，直到窗口内不再包含重复字符。使用哈希数组统计字符频率是最快的方式。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
left = , right = , n = s.();
hash[] = {};
ret = ;
(right < n) {
hash[s[right]]++;
(hash[s[right]] > ) {
hash[s[left]]--;
left++;
}
ret = (ret, right - left + );
right++;
}
ret;
}
};