滑动窗口算法实战
滑动窗口是处理区间类问题的核心技巧，通过双指针维护一个动态变化的区间，能在 O(N) 时间复杂度内解决许多暴力枚举无法胜任的题目。本文将结合 Java 语言，通过八道 LeetCode 经典题目，深入剖析双指针优化、哈希表配合及状态转换策略。
1. 长度最小的子数组
题目解析：给定正整数数组和目标值，寻找和大于等于目标值的连续最小子数组长度。
思路：暴力双重循环会遍历所有情况，但存在大量冗余。既然数组元素均为正数，一旦当前区间和满足条件，继续扩大右边界只会增加长度，因此无需保留。我们可以使用同向双指针（滑动窗口），右指针负责扩展窗口累加和，左指针负责收缩窗口以寻找最短长度。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int len = Integer.MAX_VALUE;
int n = nums.length;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right]; // 入窗口
while (sum >= target) {
len = Math.min(len, right - left + 1); // 更新结果
sum -= nums[left++]; // 出窗口
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
}
时间复杂度：O(N)，空间复杂度：O(1)
2. 无重复字符的最长子串
题目解析：在字符串 s 中找出最长连续不重复子串的长度。
思路：利用哈希表记录字符出现次数。当右指针遇到重复字符时，左指针需持续右移直到消除重复。这里为了效率，直接使用长度为 128 的整型数组模拟哈希表（基于 ASCII 码）。
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] hash = new int[128];
int len = 0;
char[] chars = s.toCharArray();
for (int left = 0, right = 0; right < chars.length; right++) {
hash[chars[right]]++; // 入窗口
while (hash[chars[right]] > 1) { // 有重复，出窗口
hash[chars[left++]]--;
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
3. 最大连续 1 的个数 III
题目解析：找到最多翻转 k 个 0 后，连续 1 的最大个数。
思路：问题可转化为'包含不超过 k 个 0 的最长子数组'。统计窗口内 0 的个数，若超过 k，则移动左指针直到合法。
class Solution {
public int longestOnes(int[] nums, int k) {
int len = 0;
int count = 0;
int n = nums.length;
for (int left = 0, right = 0; right < n; right++) {
if (nums[right] == 0) count++; // 统计 0 的个数
while (count > k) {
if (nums[left++] == 0) count--; // 出窗口
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
时间复杂度：O(N)，空间复杂度：O(1)
4. 将 x 减到 0 的最小操作数
题目解析：每次从数组两端移除数字使其和为 x，求最小操作数。
思路：正难则反。移除两端等价于保留中间一段连续子数组，且该子数组的和为 总和 - x。问题转化为寻找和为 target 的最长子数组。
class Solution {
public int minOperations(int[] nums, int x) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < n; i++) sum += nums[i];
int target = sum - x;
if (target < 0) return -1;
int total = 0;
int len = -1;
for (int left = 0, right = 0; right < n; right++) {
total += nums[right]; // 入窗口
while (total > target) {
total -= nums[left++]; // 出窗口
}
if (total == target) {
len = Math.max(len, right - left + 1);
}
}
return len == -1 ? -1 : n - len;
}
}
5. 水果成篮
题目解析：两个篮子，每个篮子只能放一种水果，不能跳过，求最多能摘多少水果。
思路：转换为'最多包含两种不同元素的最长子数组'。使用哈希表（或数组）记录每种水果数量，种类超过 2 时收缩左边界。
class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length;
int[] hash = new int[n + 1];
int len = 0;
int kinds = 0;
for (int left = 0, right = 0; right < n; right++) {
if (hash[fruits[right]] == 0) kinds++; // 新种类
hash[fruits[right]]++; // 入窗口
while (kinds > 2) {
hash[fruits[left]]--; // 出窗口
if (hash[fruits[left]] == 0) kinds--;
left++;
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
时间复杂度：O(N)，空间复杂度：O(N)
6. 找到字符串中所有字母异位词
题目解析：在 s 中找到所有 p 的异位词子串的起始索引。
思路：窗口大小固定为 p 的长度。使用两个计数数组分别记录 p 的字符频次和当前窗口的字符频次，比较是否一致即可。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ret = new ArrayList<>();
char[] sc = s.toCharArray();
char[] pc = p.toCharArray();
int[] hash1 = new int[26];
for (char ch : pc) hash1[ch - 'a']++;
int[] hash2 = new int[26];
int n = p.length();
int count = 0;
for (int left = 0, right = 0; right < s.length(); right++) {
char in = sc[right];
if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; // 有效字符入窗口
if (right - left + 1 > n) { // 窗口过大，出窗口
char out = sc[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
}
if (count == n) ret.add(left);
}
return ret;
}
}
时间复杂度：O(N+M)，空间复杂度：O(1)
7. 串联所有单词的子串
题目解析：找出包含 words 中所有单词（顺序不限）的子串起始位置。
思路：与上一题类似，只是基本单位变成了单词而非字符。由于单词长度固定，可以分 n 次滑动（n 为单词长度），每次步长为单词长度，逻辑保持一致。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret = new ArrayList<>();
Map<String, Integer> hash1 = new HashMap<>();
for (String word : words) {
hash1.put(word, hash1.getOrDefault(word, 0) + 1);
}
int n = words[0].length();
int m = words.length;
for (int i = 0; i < n; i++) {
Map<String, Integer> hash2 = new HashMap<>();
for (int left = i, right = i, count = 0; right <= s.length() - n; right += n) {
String in = s.substring(right, right + n);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if (hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
if (right - left + 1 > m * n) {
String out = s.substring(left, left + n);
if (hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
hash2.put(out, hash2.get(out) - 1);
if (hash2.get(out) == 0) hash2.remove(out);
left += n;
}
if (count == m) ret.add(left);
}
}
return ret;
}
}
时间复杂度：O(mn)，空间复杂度：O(n)*
8. 最小覆盖子串
题目解析：在 s 中找到包含 t 中所有字符的最小子串。
思路：动态窗口。右指针扩展直到满足条件，左指针收缩直到不再满足，记录过程中的最小长度。使用哈希表记录 t 中字符需求量和当前窗口满足量。
class Solution {
public String minWindow(String s, String t) {
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
int[] hash1 = new int[128];
int kinds = 0;
for (char ch : tc) {
if (hash1[ch]++ == 0) kinds++;
}
int minlen = Integer.MAX_VALUE;
int begin = -1;
int[] hash2 = new int[128];
int count = 0;
for (int left = 0, right = 0; right < s.length(); right++) {
char in = sc[right];
if (++hash2[in] == hash1[in]) count++; // 满足需求
while (kinds == count) {
if (right - left + 1 < minlen) {
begin = left;
minlen = right - left + 1;
}
char out = sc[left++];
if (hash2[out]-- == hash1[out]) count--;
}
}
return begin == -1 ? "" : s.substring(begin, begin + minlen);
}
}
时间复杂度：O(m+n)，空间复杂度：O(1)
