滑动窗口算法实战
滑动窗口是处理区间类问题的核心技巧，通过双指针维护一个动态变化的区间，能在 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 {
[] hash = [];
;
[] chars = s.toCharArray();
( , right = ; right < chars.length; right++) {
hash[chars[right]]++;
(hash[chars[right]] > ) {
hash[chars[left++]]--;
}
len = Math.max(len, right - left + );
}
len;
}
}
