算法应用场景

在算法面试中，双指针（Two Pointers） 是解决数组和链表问题降低时间复杂度的终极武器。它最神奇的地方在于：能将原本需要两层 for 循环嵌套的 O(n^2) 暴力解法，直接降维优化到 O(n)。

很多初学者觉得双指针灵活多变，一会儿从两头往中间走，一会儿快慢一起跑，容易看懂却不会自己写。其实，LeetCode Hot 100 中的双指针题目，本质上只有两个最核心的底层套路：「左右夹逼模板（对撞指针）」和「快慢同向指针模板」。

今天我们拒绝花哨的高级 API，完全用最基础的 while 循环和 if-else 逻辑，帮你彻底吃透双指针。

🚀 模板一：左右夹逼模板（对撞指针）

1. 模板抽象与核心思想

这类题目通常要求在一个排好序的数组（或者满足某种单调性）里寻找答案。

它的核心思想是：两个指针分别指向数组的头（左）和尾（右），根据当前两个指针指向的数据之和（或状态），与目标值进行对比，从而决定是让左指针右移，还是让右指针左移，像两把夹子一样向中间逼近。

// 通用基础款代码模板
int left = 0;
int right = nums.length - 1;

while (left < right) {
    // 1. 计算当前左右指针组合的状态值（比如求和）
    int currentSum = nums[left] + nums[right];
    
    // 2. 根据状态值与目标值对比，移动指针
    if (currentSum == target) {
        // 找到了答案，根据题目要求处理（返回下标或记录答案）
        left++;  // 或者 right--; 根据去重需求决定
    } else if (currentSum < target) {
        // 值小了，让左指针往右走，去碰更大的数
        left++;
    } else {
        // 值大了，让右指针往左走，去碰更小的数
        right--;
    }
}

2. Hot 100 实战演练：LeetCode 11. 盛最多水的容器

题目大意：给定一个长度为 n 的整数数组 height。找出两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

🛠️ 纯基础款代码实现

这道题的两个边界就是左右指针。容器的容量取决于 “短板”。要想换取更大的容量，只有让指向短板的那个指针向中间移动，才有可能碰到更高的板子。

class Solution {
    public int maxArea(int[] height) {
        // 1. 初始化左右指针，分别指向头尾
        int left = 0;
        int right = height.length - 1;
        int maxWater = 0; // 记录最大水量
        
        // 2. 左右指针未相遇时，持续夹逼
        while (left < right) {
            // 计算当前宽度
            int width = right - left;
            // 桶的高取决于左右两边的短板
            int currentHeight = Math.min(height[left], height[right]);
            
            // 计算当前水量
            int currentWater = width * currentHeight;
            // 更新全局最大水量
            if (currentWater > maxWater) {
                maxWater = currentWater;
            }
            
            // 3. 核心指针移动逻辑：哪边矮，就移动哪边
            if (height[left] < height[right]) {
                left++; // 左边矮，左指针右移
            } else {
                right--; // 右边矮，右指针左移
            }
        }
        
        return maxWater;
    }
}

🚀 模板二：快慢同向指针模板

1. 模板抽象与核心思想

这类题目不需要数组有序。它的核心思想是：两个指针从同一起点出发，朝着同一个方向移动。快指针（fast）走在前面，负责探路、寻找满足条件的元素；慢指针（slow）留在后面，负责维护“好数据的边界”或者记录最终结果。

// 通用基础款代码模板
int slow = 0;

for (int fast = 0; fast < nums.length; fast++) {
    // 1. 快指针在前面探路，判断当前元素是否是我们需要的“好元素”
    if (满足某种条件(nums[fast])) {
        // 2. 如果需要，把好元素原地复制到慢指针的位置
        nums[slow] = nums[fast];
        // 3. 慢指针往前走一步，扩大好元素的边界
        slow++;
    }
}
// 最终 slow 的值通常就是处理后的新数组长度

2. Hot 100 实战演练：LeetCode 283. 移动零

题目大意：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。要求必须在原数组上操作。

🛠️ 纯基础款代码实现

这道题直接套用快慢指针：快指针负责去找“不是 0 的好元素”，慢指针停留在“下一个该填入非 0 元素的位置”。

class Solution {
    public void moveZeroes(int[] nums) {
        // 1. 初始化慢指针
        int slow = 0;
        
        // 2. 快指针 fast 从头到尾负责探路
        for (int fast = 0; fast < nums.length; fast++) {
            // 如果快指针找到了一个“不是 0”的好元素
            if (nums[fast] != 0) {
                // 将快指针的值和慢指针的值进行交换
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                
                // 3. 慢指针往前走一步，代表非 0 元素的边界向右扩展
                slow++;
            }
        }
    }
}

💡 特殊衍生题型：多指针与去重防重

LeetCode 15. 三数之和

题目大意：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足i != j、i != k 且 j != k，同时满足三数之和为 0 。返回所有和为 0 且不重复的三元组。

🛠️ 怎么用普通代码写出降维打击？

三个数找组合，暴力需要三层循环 $O(n^3)$。我们可以“固定一个数，双指针找另外两个数”，直接把复杂度降到 $O(n^2)$。

这道题最大的难点是去重，基础不好的同学很容易写错。用最直白的 if 判断跳过相同数字即可。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        // 1. 左右夹逼必须先排序！
        Arrays.sort(nums);
        
        // 2. 第一层循环：固定第一个数 nums[i]
        for (int i = 0; i < nums.length - 2; i++) {
            // 核心去重：如果这个数和上一次固定的数一样，直接跳过，防止结果重复
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 3. 转化为两数之和：在接下来的区间内套用【模板一（左右夹逼）】
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    // 找到了，塞进结果集
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    
                    // 核心去重：左右指针在往中间走的时候，也要跳过相同的数
                    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;
    }
}

🛠️ 总结：双指针解题思考流

拿到一道题，怎么判定用哪种双指针？

1. 看数组是否有序 / 能否排序：

   • 如果数组是有序的，或者要求找满足某个数值关系的组合（如两数、三数之和、盛水容器）优先考虑模板一：左右夹逼指针。

   • 如果数组是无序的，且要求原地修改数组、删除特定元素、或者是在链表中（如判断环、找中点）优先考虑模板二：快慢同向指针。

2. 消灭无意义的嵌套：只要看到题目需要“通过两层循环不断比对两两元素”，就可以用两个指针对省掉一层 for 循环，将空间复杂度锁死在 O(1)。