跳到主要内容

双指针技巧

双指针（Two Pointers）是在数组或链表上常见的优化技巧。通过两个指针同向（快慢指针）或反向（对撞指针）地执行，可以将一些 O(n²) 的问题降低到 O(n)。

双指针的核心思想是利用问题的单调性或有序性，通过合理移动指针来避免不必要的枚举。常见的应用场景包括：

  • 对撞指针：两端向中间收缩，适用于有序数组或需要找配对的问题
  • 快慢指针：同向移动但速度不同，适用于链表找环、找中点等问题
  • 滑动窗口：维护一个动态窗口，适用于子串、子数组问题

283. 移动零 (Move Zeroes)​

题目描述​

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

示例 2：

输入：nums = [0]
输出：[0]

约束条件：

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

解题思路​

这道题要求将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。关键点在于原地操作和保持顺序。

方法：快慢指针​

使用两个指针：

  • 慢指针 slow：指向下一个非零元素应该存放的位置
  • 快指针 fast：遍历整个数组

遍历过程中，每当 fast 指针遇到非零元素，就将其交换到 slow 位置，然后 slow 前进一位。这样所有非零元素会被依次移到数组前部，零元素自然留在末尾。

图解示例​

以 nums = [0,1,0,3,12] 为例：

初始状态：
nums = [0, 1, 0, 3, 12]
        ^        ^
      slow=0   fast=0

第1步：nums[0]=0，跳过交换
nums = [0, 1, 0, 3, 12]
        ^     ^
      slow=0  fast=1

第2步：nums[1]=1≠0，交换到slow位置
nums = [1, 0, 0, 3, 12]
           ^  ^
         slow=1 fast=2

第3步：nums[2]=0，跳过交换
nums = [1, 0, 0, 3, 12]
           ^     ^
         slow=1  fast=3

第4步：nums[3]=3≠0，交换到slow位置
nums = [1, 3, 0, 0, 12]
              ^  ^
            slow=2 fast=4

第5步：nums[4]=12≠0，交换到slow位置
nums = [1, 3, 12, 0, 0]
                  ^
                slow=3

完成！所有非零元素已移到前部，零元素在末尾

Java 代码实现​

class Solution {
    public void moveZeroes(int[] nums) {
        // 慢指针：指向下一个非零元素应存放的位置
        int slow = 0;
        
        // 快指针：遍历数组
        for (int fast = 0; fast < nums.length; fast++) {
            // 当遇到非零元素时
            if (nums[fast] != 0) {
                // 交换快慢指针位置的元素
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                // 慢指针前进
                slow++;
            }
        }
    }
}

复杂度分析​

时间复杂度：O(n)，其中 n 是数组长度。快指针遍历数组一次。

空间复杂度：O(1)，只使用了常数级别的额外空间。

优化写法​

上面的交换操作在 fast == slow 时是多余的，可以优化：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                // 只有当快慢指针不同时才交换
                if (fast != slow) {
                    nums[slow] = nums[fast];
                    nums[fast] = 0;
                }
                slow++;
            }
        }
    }
}

11. 盛最多水的容器 (Container With Most Water)​

题目描述​

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

约束条件：

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

解题思路​

这道题的关键是理解容器容量的计算方式：容量 = 两条线之间的距离 × 较短线的高度。

方法一：暴力枚举（不推荐）​

枚举所有可能的两条线组合，计算最大容量。时间复杂度 O(n²)，会超时。

方法二：对撞指针（推荐）​

使用左右两个指针从两端向中间收缩。每次移动较短的那根柱子，因为：

  • 容量受限于较短柱子的高度
  • 如果移动较长柱子，宽度减小，高度不可能增加，容量一定减小
  • 移动较短柱子，有可能找到更高的柱子，从而增加容量

图解示例​

以 height = [1,8,6,2,5,4,8,3,7] 为例：

初始状态：left=0, right=8
height: [1, 8, 6, 2, 5, 4, 8, 3, 7]
          ^                    ^
        left=0               right=8

计算面积：min(1,7) × (8-0) = 1 × 8 = 8
移动较短边：left++（因为 1 < 7）

第2步：left=1, right=8
height: [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ^                 ^
           left=1            right=8

计算面积：min(8,7) × (8-1) = 7 × 7 = 49 ← 最大值！
移动较短边：right--（因为 7 < 8）

第3步：left=1, right=7
height: [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ^              ^
           left=1         right=7

计算面积：min(8,3) × (7-1) = 3 × 6 = 18
移动较短边：right--

...继续收缩直到 left >= right...

最终最大容量：49

Java 代码实现​

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // 计算当前容器容量
            // 宽度 = right - left
            // 高度 = min(height[left], height[right])
            int currentArea = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, currentArea);
            
            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

复杂度分析​

时间复杂度：O(n)，双指针最多遍历数组一次。

空间复杂度：O(1)，只使用了常数级别的额外空间。

为什么移动较短边是正确的？​

这是一个关键问题。假设 height[left] < height[right]：

  • 如果移动 right（较长边）：宽度变小，高度最多是 height[left]（受限较短边），容量必然减小
  • 如果移动 left（较短边）：宽度变小，但高度可能增加（如果新 height[left] 更大），容量有可能增大

因此，移动较短边才有可能找到更大的容量。

15. 三数之和 (3Sum)​

题目描述​

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

约束条件：

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

解题思路​

这道题要求找出所有和为 0 的三元组，且不能有重复。核心挑战在于去重。

方法：排序 + 双指针​

  1. 排序：先对数组排序，这样可以方便去重和使用双指针
  2. 固定一个数：遍历数组，将 nums[i] 作为三元组的第一个数
  3. 双指针找配对：在 i 右侧用双指针找两个数，使三数之和为 0
  4. 去重处理：跳过重复的元素

图解示例​

以 nums = [-1,0,1,2,-1,-4] 为例：

第一步：排序
nums = [-4, -1, -1, 0, 1, 2]

第二步：遍历 + 双指针

i=0, nums[i]=-4:
  left=1, right=5
  sum = -4 + (-1) + 2 = -3 < 0 → left++
  left=2, right=5
  sum = -4 + (-1) + 2 = -3 < 0 → left++
  left=3, right=5
  sum = -4 + 0 + 2 = -2 < 0 → left++
  left=4, right=5
  sum = -4 + 1 + 2 = -1 < 0 → left++
  left=5, right=5，结束本轮

i=1, nums[i]=-1:
  left=2, right=5
  sum = -1 + (-1) + 2 = 0 ✓ 找到 [-1, -1, 2]
  left=3, right=4
  sum = -1 + 0 + 1 = 0 ✓ 找到 [-1, 0, 1]
  left=4, right=3，结束本轮

i=2, nums[i]=-1:
  与前一个元素相同，跳过（去重）

i=3, nums[i]=0:
  left=4, right=5
  sum = 0 + 1 + 2 = 3 > 0 → right--
  left=4, right=4，结束本轮

结果：[[-1,-1,2], [-1,0,1]]

Java 代码实现​

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        // 第一步：排序，为双指针和去重做准备
        Arrays.sort(nums);
        
        // 第二步：遍历数组，固定第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 提前终止：如果最小的数都大于0，三数之和不可能为0
            if (nums[i] > 0) break;
            
            // 去重：跳过相同的第一个数
            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) {
                    // 和太小，需要更大的数，左指针右移
                    left++;
                } else if (sum > 0) {
                    // 和太大，需要更小的数，右指针左移
                    right--;
                } else {
                    // 找到一组解
                    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--;
                }
            }
        }
        
        return result;
    }
}

复杂度分析​

时间复杂度：O(n²)

  • 排序：O(n log n)
  • 外层循环 O(n) × 内层双指针 O(n) = O(n²)
  • 总体：O(n²)

空间复杂度：O(log n)

  • 排序需要 O(log n) 的栈空间（不考虑输出数组）

易错点​

  1. 去重顺序：找到解后，先跳过重复元素，再移动指针
  2. 边界条件：第一个数去重时要检查 i > 0
  3. 提前终止：当 nums[i] > 0 时可以提前结束

42. 接雨水 (Trapping Rain Water)​

题目描述​

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

约束条件：

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

解题思路​

这道题的核心在于理解：每个位置能接多少雨水，取决于它左右两边最高柱子的较小值。

对于位置 i：

  • 左边最高柱子：leftMax[i] = max(height[0], height[1], ..., height[i])
  • 右边最高柱子：rightMax[i] = max(height[i], height[i+1], ..., height[n-1])
  • 该位置能接的雨水：min(leftMax[i], rightMax[i]) - height[i]

方法一：动态规划​

用两个数组分别预处理每个位置左右两边的最大高度。

方法二：双指针（空间优化）​

观察发现，我们不需要同时知道左右两边的最大高度，只需要知道较小的一边。可以用双指针从两端向中间遍历，同时维护左右最大值。

图解示例​

以 height = [3, 0, 2, 0, 4] 为例：

柱子高度：  3   0   2   0   4
位置：      0   1   2   3   4

计算每个位置的左右最大高度：

位置  左边最高  右边最高  min(左,右)  当前高度  可接雨水
 0      3        4         3          3        0
 1      3        4         3          0        3
 2      3        4         3          2        1
 3      3        4         3          0        3
 4      4        4         4          4        0

总计：0 + 3 + 1 + 3 + 0 = 7

图示：
    |        |
    |   ≈≈≈  |
    | ≈ | ≈≈≈ |
    |___|_____|

≈ 表示雨水

Java 代码实现​

方法一：动态规划

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        
        int n = height.length;
        
        // leftMax[i] 表示位置 i 及其左边的最大高度
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        
        // rightMax[i] 表示位置 i 及其右边的最大高度
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        
        // 计算每个位置能接的雨水
        int totalWater = 0;
        for (int i = 0; i < n; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return totalWater;
    }
}

方法二：双指针（空间优化）

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;
        
        while (left < right) {
            // 更新左右最大值
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            
            // 较小的一边决定水位
            if (height[left] < height[right]) {
                // 左边较低，左边水位由 leftMax 决定
                totalWater += leftMax - height[left];
                left++;
            } else {
                // 右边较低，右边水位由 rightMax 决定
                totalWater += rightMax - height[right];
                right--;
            }
        }
        
        return totalWater;
    }
}

复杂度分析​

方法一（动态规划）：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

方法二（双指针）：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

双指针方法为什么正确？​

关键观察：当 height[left] < height[right] 时：

  • leftMax 一定小于等于 rightMax（因为 rightMax 至少是 height[right]）
  • 所以位置 left 的水位由 leftMax 决定
  • 我们可以安全地计算 left 位置的雨水，然后移动 left

同理，当 height[left] >= height[right] 时，可以计算 right 位置的雨水。

相关题目​