三数之和

问题

给定一个整数数组 nums，找出所有和为 0 的三元组 [nums[i], nums[j], nums[k]]，要求 i ≠ j ≠ k，且结果不能包含重复的三元组。

示例：

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

解答

暴力解法（O(n³)）

function threeSum(nums) {
  const result = [];
  const n = nums.length;
  nums.sort((a, b) => a - b); // 排序便于去重

  for (let i = 0; i < n - 2; i++) {
    // 跳过重复元素
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    for (let j = i + 1; j < n - 1; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;

      for (let k = j + 1; k < n; k++) {
        if (k > j + 1 && nums[k] === nums[k - 1]) continue;

        if (nums[i] + nums[j] + nums[k] === 0) {
          result.push([nums[i], nums[j], nums[k]]);
        }
      }
    }
  }

  return result;
}

排序 + 双指针（O(n²)）

function threeSum(nums) {
  const result = [];
  const n = nums.length;

  // 排序是双指针的前提
  nums.sort((a, b) => a - b);

  for (let i = 0; i < n - 2; i++) {
    // 最小值大于 0，后面不可能有解
    if (nums[i] > 0) break;

    // 跳过重复的第一个数
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = n - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([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;
}

测试

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]

console.log(threeSum([0, 0, 0, 0]));
// [[0, 0, 0]]

console.log(threeSum([1, 2, -3, 4, -2, -1]));
// [[-3, -1, 4], [-3, 1, 2], [-2, -1, 3]] — 取决于输入

关键点

• 先排序：排序后才能使用双指针，也便于去重
• 固定一个数：外层循环固定第一个数，内层用双指针找另外两个
• 双指针移动：和小于 0 左移，和大于 0 右移
• 去重处理：三个位置都要跳过重复元素，避免重复三元组
• 剪枝优化：第一个数大于 0 时可直接退出