算法模式：双指针

D瓜哥
算法
算法模式：双指针

在上一篇文章 算法模式：区间合并 介绍了合并区间所用的算法模式。本篇文章，介绍一个即可以用在数组，又可以用在链表中的算法模式：双指针。

双指针

双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。

需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效，但时间复杂度一般会是 \$O(n^2)\$。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。

识别使用双指针的招数：

  • 一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件

  • 这种组合可能是一对数，三个数，或是一个子数组

LeetCode 15. 三数之和

LeetCode - 15. 三数之和

给你一个整数数组 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

  • -105<= nums[i] <= 105

思路分析

在一个数组中，查找三个数之和，有很多种办法。如果考虑双指针的解法，那么，可以对数组进行排序，取出一个数字，然后使用两个指针，在剩余数组中，分别指向数组首尾，根据之和的大小，来移动指针。代码如下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-06 16:53:23
 */
public List<List<Integer>> threeSum(int[] nums) {
  Arrays.sort(nums);
  return numsSum(nums, 0, 3, 0);
}

/**
 * 通用方法，可以处理 count 数之和
 */
private List<List<Integer>> numsSum(int[] nums, int idx, int count, int sum) {
  // 剩余数组长度不够，直接返回
  if (nums.length - idx < count || count < 2) {
    return new ArrayList<>();
  }
  List<List<Integer>> result = new ArrayList<>();
  if (count == 2) {
    int left = idx, right = nums.length - 1;
    while (left < right) {
      int leftNum = nums[left];
      int rightNum = nums[right];
      int iSum = leftNum + rightNum;
      if (iSum == sum) {
        result.add(new ArrayList<>(Arrays.asList(leftNum, rightNum)));
        // 不允许有重复数组，则将重复元素都排除掉
        while (left < right && leftNum == nums[left]) {
          left++;
        }
        while (left < right && rightNum == nums[right]) {
          right--;
        }
      } else if (iSum < sum) {
        while (left < right && leftNum == nums[left]) {
          left++;
        }
      } else {
        while (left < right && rightNum == nums[right]) {
          right--;
        }
      }
    }
    return result;
  } else {
    for (int i = idx; i < nums.length; i++) {
      int num = nums[i];
      // 在这里，递归相当一层循环，无论 count 值多大，就可以通过增加递归次数，来降低 count 的值
      List<List<Integer>> lists = numsSum(nums, i + 1, count - 1, sum - num);
      for (List<Integer> list : lists) {
        list.add(num);
        result.add(list);
      }
      // 不允许有重复数组，则将重复元素都排除掉
      // 使用 nums[i] == nums[i + 1] 来判断，因为执行完该语句之后，还有一个 i++ 要执行
      while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
        i++;
      }
    }
  }
  return result;
}