跳到主要内容

双指针技巧

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

283. 移动零 (Move Zeroes)​

题目描述​

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在原数组上操作，不能拷贝额外的数组。

解题思路​

使用快慢指针。慢指针 slow 指向下一个非零元素应存放的位置，快指针 fast 遍历数组。每当 nums[fast] 不为 0 时，将其与 nums[slow] 交换，并使 slow 自增。

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++;
            }
        }
    }
}

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

题目描述​

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

解题思路​

使用左右指针对撞。容器面积由 (right - left) * min(height[left], height[right]) 决定。为了寻找更大的面积，我们每次移动较短的那一根柱子（因为移动长柱子面积只会减小）。

Java 代码实现​

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < 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;
    }
}

15. 三数之和 (3sum)​

题目描述​

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

解题思路​

  1. 数组先排序。
  2. 固定一个数 nums[i]，在其右侧范围内使用双指针 L 和 R 寻找 nums[L] + nums[R] == -nums[i]。
  3. 注意去重处理。

Java 代码实现​

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int L = i + 1, R = nums.length - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while (L < R && nums[L] == nums[L + 1]) L++;
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    L++; R--;
                } else if (sum < 0) L++;
                else R--;
            }
        }
        return res;
    }
}

42. 接雨水 (Trapping Rain Water)​

题目描述​

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

解题思路​

双指针法。维护 leftMax 和 rightMax。如果 height[left] < height[right]，则左侧高度受限于 leftMax，可以结算左侧位置并移动 left 指针；反之结算右侧。

Java 代码实现​

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int res = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                res += leftMax - height[left];
                left++;
            } else {
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}