滑动窗口与双指针：把 O(n²) 降维成 O(n) 的魔法

哈喽，大家好呀，我是蔚蓝 ，今天我们来聊聊面试中出场率最高的两个算法技巧：滑动窗口和双指针。

LeetCode 提交页面，红色的「Time Limit Exceeded」。

你写过两层 for 循环嵌套吗？逻辑没问题，就是跑不完。

我刷题的时候经常这样。一道数组题，暴力解法写完，自以为稳了，一点提交，结果超时。那个感觉，像考试写满了一整页，最后发现审错题。

后来我发现，很多「连续子序列」的问题，根本不需要两层循环。一个技巧能救命：滑动窗口。

滑动窗口：一条贪吃蛇的自我修养

想象一条贪吃蛇。

它在数组上爬行，头往右伸，吃到新元素。身体太长了？尾巴缩一缩。始终保持一个「窗口」，窗口里的东西满足某个条件。

这就是滑动窗口。

核心四个字：一进一出。

右指针负责「进」，把新元素拉进窗口。左指针负责「出」，把老元素踢出去。两个指针配合，窗口就在数组上滑起来了。

滑动窗口四步曲

我把它总结成四步，背下来，遇到题目直接套：

  1. 枚举右端点：for 循环让 right 往右走，新元素入窗
  2. 维护窗口：窗口不满足条件时，while 循环调整
  3. 更新左端点：在 while 里移动 left，元素出窗
  4. 更新答案：窗口满足条件后，记录结果

四步走完，一轮循环结束。

光说不练假把式。上例子。

长度最小的子数组

题目：找和 ≥ target 的最短连续子数组。

暴力怎么做？两层循环枚举所有子数组，算和，记录最小长度。O(n²)，提交必挂。

滑动窗口怎么做？ 

1
2
3
4
5
6
7
8
9
10
11
public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, ans = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];          // 1. 入
        while (sum >= target) {      // 2. 维护
            ans = Math.min(ans, right - left + 1);  // 4. 更新答案
            sum -= nums[left++];     // 3. 出
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

看懂了吗？

右指针不断往右吃，累加和。一旦和够了，就试着收缩左边界——也许左边少一个元素，和还是够的，那窗口就能更短。

求最小长度，在 while 里更新答案。

时间复杂度？每个元素最多进窗一次、出窗一次。O(n)。

从 n² 到 n，这就是降维打击。

乘积小于 K 的子数组

题目：统计乘积 < k 的连续子数组个数。

这题有个坑点：求的是「个数」不是「长度」。

1
2
3
4
5
6
7
8
9
10
11
12
public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int left = 0, prod = 1, ans = 0;
    for (int right = 0; right < nums.length; right++) {
        prod *= nums[right];         // 1. 入
        while (prod >= k) {          // 2. 维护
            prod /= nums[left++];    // 3. 出
        }
        ans += right - left + 1;     // 4. 更新答案
    }
    return ans;
}

关键在 ans += right - left + 1。

为什么？

窗口 [left, right] 里所有子数组都满足条件。以 right 结尾的子数组有多少个？right - left + 1 个。

画个图就明白了：[left, right]、[left+1, right]、[left+2, right]……一直到 [right, right]。

求子数组个数，用这个公式。

定长窗口：不需要 while

有些题目窗口大小是固定的。比如「长度为 k 的子串中最多有几个元音」。

定长窗口更简单。不需要 while 收缩，直接用 if 判断窗口大小就行。

1
2
3
4
5
6
7
8
9
10
public int maxVowels(String s, int k) {
    int ans = 0, count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (isVowel(s.charAt(i))) count++;      // 入
        if (i < k - 1) continue;                 // 窗口未满
        ans = Math.max(ans, count);              // 更新答案
        if (isVowel(s.charAt(i - k + 1))) count--; // 出
    }
    return ans;
}

入、满、更、出。顺序别搞反了。

双指针：两个方向，两种打法

滑动窗口本质上是双指针的一种——同向双指针。

双指针还有另一种：相向双指针。

同向双指针

两个指针朝同一个方向走。典型场景：

  • 判断子序列：一个指针扫 s，一个指针扫 t，匹配上才前进
  • 链表找环：快慢指针，快的追上慢的就是有环
  • 数组去重：排序后，慢指针指向不重复的位置

判断子序列的代码：

1
2
3
4
5
6
7
8
public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) i++;  // 匹配成功，i 才走
        j++;                                   // j 始终走
    }
    return i == s.length();
}

s 是 t 的子序列吗？让两个指针各自扫一遍，匹配成功的数量等于 s 的长度，就是。

相向双指针

两个指针从两端往中间走。

前提：数组必须有序。

典型场景：两数之和、三数之和、盛水容器。

两数之和：

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

为什么这样做是对的？

数组有序。和太小，只有增大左边界才能让和变大。和太大，只有减小右边界才能让和变小。

没有第三种选择。

这就是有序数组的美妙之处：每次决策都是确定的，不需要回溯。

三数之和：相向双指针 + 去重

三数之和是两数之和的升级版。固定一个数，剩下两个用双指针找。

难点在去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;  // i 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[++left]);  // left 去重
                while (left < right && nums[right] == nums[--right]); // right 去重
            }
        }
    }
    return ans;
}

去重有三处：i、left、right。

while (left < right && nums[left] == nums[++left]); 这行代码的意思是：跳过所有重复的 left，停在不重复的那个位置。

去重是三数之和的命门。面试官最爱问：为什么要去重？不去重会怎样？

盛水容器：贪心的艺术

题目：选两条线，和 x 轴围成容器，求最大面积。

面积 = min(左高, 右高) × 宽度。

两个指针从两端往中间缩。谁短移谁。

为什么？

宽度在缩小。只有换掉短的那条边，才可能找到更高的板子来补偿宽度损失。

1
2
3
4
5
6
7
8
9
10
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1, ans = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        ans = Math.max(ans, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return ans;
}

这题的贪心策略很漂亮：每次都舍弃「不可能更优」的选项。

速查表

类型 指针方向 典型场景 关键技巧
滑动窗口 同向 连续子序列 while 收缩 + 四步曲
同向双指针 同向 子序列判断、链表环 快慢指针
相向双指针 相向 有序数组找数 谁小移谁

碎碎念

滑动窗口和双指针，说白了就是让指针替你记住信息。

左指针走到哪了，窗口里的和是多少，乘积是多少……这些状态帮你省掉了内层循环。暴力解法每次都从头算，双指针只在上一次的基础上微调。

差距就在这。

刷题的时候，看到「连续子数组」「子串」「有序数组」「两数之和」这些关键词，条件反射地想到双指针。

把 O(n²) 降维成 O(n)，就靠它了。

本文涉及的题目：209. 长度最小的子数组、713. 乘积小于 K 的子数组、3. 无重复字符的最长子串、1456. 定长子串中元音字母的最大数目、1004. 最大连续 1 的个数 III、15. 三数之和、18. 四数之和、167. 两数之和 II、392. 判断子序列、11. 盛最多水的容器