双指针与滑动窗口：从「暴力枚举」到「线性扫描」的思维跃迁

场景引入：一道看似简单的数组题

技术面试中，经常遇到一类问题：在一个有序数组中找到两数之和等于目标值。许多候选人第一反应是双重循环枚举，时间复杂度 O(n²)。在数据量小的时候这或许能通过，但当数组长度达到 10⁵ 量级，O(n²) 的算法会直接超时。这时，双指针 往往能将其优化到 O(n)。

但双指针的价值远不止于此。它不仅是「从两端向中间靠拢」的固定套路，更是一种 「利用数据有序性/单调性消除无效计算」 的思维模式。本文将通过 LeetCode 热题，逐步拆解这一思想，并延伸到滑动窗口技巧，展示它们如何在看似无关的题目中形成闭环。

第一题：两数之和 II - 输入有序数组（LeetCode 167）

题目描述：给定一个已按升序排列的整数数组 numbers 和一个目标值 target，请找出两个数使得它们的和等于 target，返回它们的下标（从 1 开始计数）。

解题思路推导：暴力解法是枚举所有组合，但有序数组给了重要线索——当 left 指向最小值、right 指向最大值时，若 sum < target，说明 left 太小，右移 left 才能增大和；若 sum > target，说明 right 太大，左移 right 减小和。每一次比较都能排除一个候选元素，因此总扫描次数不超过数组长度。

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}; // 题目要求下标从1开始
        } else if (sum < target) {
            left++;      // 和太小，需要更大的数
        } else {
            right--;     // 和太大，需要更小的数
        }
    }
    return new int[]{-1, -1}; // 题目保证有解，此处仅为编译需要
}

关键点与踩坑提示：核心在于 left 和 right 的移动逻辑——每次移动必须基于「当前和与目标值的比较结果」，而不能盲目移动。另一个常见错误是忘记题目要求下标从 1 开始，导致返回 [left, right] 而非 [left+1, right+1]。

复杂度分析：时间复杂度 O(n)（每步排除一个元素），空间复杂度 O(1)。相比暴力 O(n²)，这是质的飞跃。

自然延伸：从「两数之和」到「三数之和」（LeetCode 15）

既然双指针能解决两数之和，那么三数之和是否也能套用？答案是肯定的，但需要先固定一个数，再用双指针处理剩余的两个数。这就是 「固定一个 + 双指针扫剩余」 的典型模式。

题目描述：给定一个包含 n 个整数的数组 nums，判断是否存在三个元素 a、b、c，使得 a + b + c = 0，找出所有不重复的三元组。

解题思路推导：首先对数组排序（排序让双指针得以使用）。遍历数组，固定 nums[i] 作为第一个数，然后在 i+1 到末尾的区间内用双指针找两数之和等于 -nums[i]。注意去重：当 nums[i] 与前一个元素相等时跳过，避免重复三元组。

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue; // 跳过重复的固定值
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left+1]) left++; // 跳过重复
                while (left < right && nums[right] == nums[right-1]) right--; // 跳过重复
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

关键点与踩坑提示：去重逻辑是本题最容易出错的地方。固定值去重 和 双指针移动后的去重 必须同时处理，否则会产生重复结果。另外，排序是前提，直接对原数组排序会改变原始数据，若后续还需使用原数组需注意拷贝。

复杂度分析：排序 O(n log n)，遍历固定值 O(n) 且每次双指针扫描 O(n)，总时间复杂度 O(n²)。空间复杂度 O(1)（不计输出结果）。

滑动窗口：双指针的「兄弟技巧」

双指针解决的是「两端收缩」问题，而 滑动窗口 解决的则是「同向移动」问题——left 和 right 都从起点出发，right 先扩展窗口，left 在条件不满足时收缩窗口。这本质上是双指针的另一种形态，常用于子数组/子串问题。

题目描述（LeetCode 209 长度最小的子数组）：给定一个正整数数组 nums 和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。

解题思路推导：暴力枚举每个起点和终点需要 O(n²)。滑动窗口利用 「右指针扩展、左指针收缩」 维护一个动态窗口：当窗口和 ≥ target 时，记录长度并尝试收缩左边界，看能否找到更短解。因为数组全为正数，收缩窗口会减小和，所以这种策略是正确的。

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

关键点与踩坑提示：while 循环而非 if 判断是本题的关键——因为收缩可能连续进行多次，直到窗口和再次小于 target。若写成 if，会漏掉某些更短的子数组。另外，minLen 初始化为 Integer.MAX_VALUE，最后检查是否被更新过，若未更新则返回 0。

复杂度分析：每个元素最多被 right 和 left 各访问一次，时间复杂度 O(n)。空间复杂度 O(1)。

关联题目与进阶思考

滑动窗口的变体非常丰富，常见的有：

LeetCode 3 无重复字符的最长子串：用哈希表记录字符最后出现位置，left 跳跃式移动。
LeetCode 76 最小覆盖子串：窗口内字符计数与目标串匹配，需要维护一个 counter 变量。
LeetCode 424 替换后的最长重复字符：窗口内「最多允许 k 个其他字符」的条件判断。

这些题目的共同点是：窗口的扩展与收缩都遵循「右进左出」的单调性，且条件判断往往用哈希表或计数数组辅助。理解了这一点，就能从「背模板」升级为「按需设计」。

总结与下一步行动

本文从最基础的两数之和出发，展示了双指针如何从「两端收缩」优化暴力枚举，进而延伸到三数之和的「固定 + 双指针」模式，最后引入滑动窗口作为双指针的同向变体。核心收获有三点：

有序是双指针的前提——遇到无序数组，先考虑排序是否影响答案。
滑动窗口适用于子数组/子串的连续性问题——条件满足时收缩，不满足时扩展。
去重与边界条件是双指针题目的主要坑点——写代码前先想清楚「指针移动的条件」和「重复情况的处理」。

下一步行动建议：建议在 LeetCode 题库中按以下顺序练习：167 → 15 → 209 → 3 → 76。每道题先独立尝试 20 分钟，再对照官方题解分析自己的思路盲区。重点记录「为什么想到用双指针/滑动窗口」的触发条件，而非仅仅记住代码。当能在一分钟内识别出「这题适合双指针还是滑动窗口」，这类问题在面试中就不再是拦路虎。

本文关键词：双指针、滑动窗口、LeetCode 167、LeetCode 15、LeetCode 209