滑动窗口

一、什么是滑动窗口？

滑动窗口是双指针的一种高级用法，专门用来解决数组/字符串的连续子序列问题。

想象一个窗口在数组上从左向右滑动：

• 左指针：左边界 left
• 右指针：右边界 right
• 窗口范围：[left, right]

核心思想：固定一个指针，移动另一个指针，动态维护窗口内的数据，避免重复计算。

二、适用场景（必考）

凡是题目出现这些关键词，优先想滑动窗口：

• 连续子数组 / 连续子串
• 最长 / 最短
• 满足条件（和、积、无重复、包含）
• 数组、字符串

三、滑动窗口通用代码模板（背会！）

// 滑动窗口万能模板
public int slidingWindow(int[] nums) {
    int left = 0;     // 左指针
    int max = 0;      // 结果
    
    // 右指针一直往前走，遍历整个数组
    for (int right = 0; right < nums.length; right++) {
        
        // 1. 把当前元素加入窗口
        
        // 2. 判断窗口是否需要收缩（不满足条件时）
        while (窗口 不合法 / 超标) {
            // 移除 left 位置元素
            left++;
        }
        
        // 3. 此时窗口合法，更新答案
        max = Math.max(max, right - left + 1);
    }
    return max;
}

---

四、最常考 3 道题（面试高频）

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

题目：给定一个字符串，返回无重复字符的最长连续子串长度。

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0;
    int max = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // 有重复，收缩左边界
        while (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        
        set.add(c);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

---

2. 长度最小的子数组（LeetCode 209）

题目：找出数组中和 ≥ target 的长度最小的连续子数组。

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int min = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        
        // 满足条件，尝试缩小窗口
        while (sum >= target) {
            min = Math.min(min, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

---

3. 滑动窗口最大值（LeetCode 239）

题目：给定一个数组和窗口大小 k，输出每个窗口的最大值。

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int[] res = new int[nums.length - k + 1];
    int index = 0;
    
    for (int right = 0; right < nums.length; right++) {
        // 维护递减队列
        while (!deque.isEmpty() && nums[right] > nums[deque.peekLast()]) {
            deque.pollLast();
        }
        deque.offerLast(right);
        
        // 超出窗口左边界，移除
        while (deque.peekFirst() <= right - k) {
            deque.pollFirst();
        }
        
        // 窗口形成，记录最大值
        if (right >= k - 1) {
            res[index++] = nums[deque.peekFirst()];
        }
    }
    return res;
}

---

五、滑动窗口优点（面试必说）

1. 时间复杂度 O(n)，只遍历一次数组
2. 空间复杂度 O(1) 或很小
3. 避免暴力法 O(n²) 的重复计算
4. 专门解决连续子数组/子串问题

---

六、总结

1. 滑动窗口 = 左右双指针 + 动态维护窗口
2. right 一直走，left 按需收缩
3. 适用：连续、最长、最短、满足条件
4. 背会模板，所有题都能套

总结

• 滑动窗口：双指针动态维护一个连续区间，解决连续子数组/子串问题。
• 核心：右指针遍历，左指针收缩窗口，保证窗口合法。
• 复杂度：O(n)，比暴力法高效很多。