3Sum（三数之和）

题目 / Problem

中文： 给定一个整数数组 nums，返回所有满足以下条件的三元组 [nums[i], nums[j], nums[k]]：

• i != j、i != k 且 j != k，即三个元素来自不同下标。
• nums[i] + nums[j] + nums[k] == 0。

答案中不能包含重复的三元组。三元组内部的顺序和最终答案的顺序都不重要。

English: Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

The solution set must not contain duplicate triplets. The order of the triplets and the order of values within each triplet do not matter.

示例 / Examples

Example 1

Input:  nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

满足条件的不同三元组为：
The distinct valid triplets are:

[-1, -1, 2] → -1 + -1 + 2 = 0
[-1,  0, 1] → -1 +  0 + 1 = 0

虽然不同的下标组合可能产生相同的三个数，但结果中每种数值组合只能出现一次。
Different index combinations may produce the same three values, but each value combination may appear only once in the result.

Example 2

Input:  nums = [0,1,1]
Output: []

唯一可能的三元组之和为 2，因此没有答案。
The only possible triplet sums to 2, so there is no answer.

Example 3

Input:  nums = [0,0,0]
Output: [[0,0,0]]

三个不同下标上的 0 可以组成和为 0 的三元组。
The three zeros at distinct indices form a triplet whose sum is 0.

约束 / Constraints

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

解题思路：排序 + 双指针 / Approach: Sorting + Two Pointers

首先将数组按数值升序排列。然后依次固定三元组中的第一个数 sorted[i]，问题就转化为：
First sort the array in ascending numeric order. Then fix the first value sorted[i], reducing the problem to:

在 i 右侧的有序区间中寻找两个数，使它们的和等于 -sorted[i]。
Find two values to the right of i whose sum equals -sorted[i].

使用两个指针：
Use two pointers:

• left = i + 1，从剩余区间左侧开始。
  left = i + 1, starting at the left of the remaining range.
• right = sorted.length - 1，从数组末尾开始。
  right = sorted.length - 1, starting at the end.

计算：
Calculate:

sum = sorted[i] + sorted[left] + sorted[right]

• 如果 sum < 0，总和太小，需要增大，因此将 left 右移。
  If sum < 0, the sum is too small, so move left right to increase it.
• 如果 sum > 0，总和太大，需要减小，因此将 right 左移。
  If sum > 0, the sum is too large, so move right left to decrease it.
• 如果 sum === 0，记录三元组，然后同时移动两个指针并跳过重复值。
  If sum === 0, record the triplet, move both pointers, and skip duplicate values.

由于始终满足 i < left < right，三个元素一定来自不同下标。
Because i < left < right always holds, the three values necessarily come from distinct indices.

去重规则 / Duplicate-Skipping Rules

排序会让相同数值相邻，从而可以直接跳过重复项：
Sorting places equal values next to each other, making duplicates easy to skip:

1. 固定第一个数时，如果 sorted[i] === sorted[i - 1]，跳过当前 i。
   When choosing the first value, skip i if sorted[i] === sorted[i - 1].
2. 找到一个有效三元组后，移动 left 并跳过与前一个左值相同的元素。
   After finding a valid triplet, advance left past duplicate left values.
3. 同时移动 right 并跳过与前一个右值相同的元素。
   Move right past duplicate right values as well.

第一条规则防止以相同首元素重复搜索；后两条规则防止同一个首元素下产生重复的后两个数。
The first rule avoids repeating searches for the same first value; the other two prevent duplicate pairs for that fixed value.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < sorted.length - 2; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) {
      continue;
    }

    if (sorted[i] > 0) {
      break;
    }

    let left = i + 1;
    let right = sorted.length - 1;

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

      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        result.push([sorted[i], sorted[left], sorted[right]]);
        left++;
        right--;

        while (left < right && sorted[left] === sorted[left - 1]) {
          left++;
        }

        while (left < right && sorted[right] === sorted[right + 1]) {
          right--;
        }
      }
    }
  }

  return result;
}

这里先使用 [...nums] 复制数组，避免 sort() 修改原始输入。
[...nums] copies the array first so that sort() does not modify the original input.

为什么 sorted[i] > 0 时可以停止？ / Why Stop When sorted[i] > 0?

数组已经升序排列。如果固定的第一个数大于 0，它右侧的所有数也都大于或等于它，因此三个数之和必然大于 0，不可能再找到答案。
The array is sorted. If the fixed first value is greater than 0, every value to its right is at least as large, so any resulting triplet has a positive sum and cannot be valid.

注意判断条件必须是 > 0，不能是 >= 0，因为 [0,0,0] 是有效答案。
The condition must be > 0, not >= 0, because [0,0,0] is a valid triplet.

执行过程 / Walkthrough

以 Example 1 为例，排序后：
For Example 1, after sorting:

[-4, -1, -1, 0, 1, 2]

固定 -4 / Fix -4

没有找到三元组。
No valid triplet is found.

固定第一个 -1 / Fix the First -1

固定第二个 -1 / Fix the Second -1

它与前一个固定值相同，因此直接跳过，避免重复答案。
It equals the previous fixed value, so skip it to avoid duplicate answers.

最终结果为：
The final result is:

[[-1,-1,2],[-1,0,1]]

复杂度 / Complexity

设数组长度为 n。
Let the array length be n.

• 排序需要 O(n log n) 时间。
  Sorting takes O(n log n) time.
• 外层循环执行 O(n) 次，每次双指针最多扫描 O(n) 个位置。
  The outer loop runs O(n) times, and the two pointers scan at most O(n) positions each time.
• 总时间复杂度：O(n²)。
  Total time: O(n²).
• 额外空间复杂度：O(n)，本实现复制了输入数组；不计算返回结果。
  Extra space: O(n) because this implementation copies the input array, excluding the returned result.

如果允许直接排序并修改 nums，则复制数组的 O(n) 空间可以省略；排序算法自身的额外空间取决于 JavaScript 引擎实现。
If modifying nums is allowed, the O(n) copy can be omitted; the sort's own extra space depends on the JavaScript engine.

暴力解法对比 / Brute-Force Comparison

暴力解法枚举三个不同下标，需要三层循环，时间复杂度为 O(n³)。当 n = 3000 时，这会产生数量巨大的组合，无法通过。
The brute-force approach enumerates three distinct indices with three nested loops, taking O(n³) time. At n = 3000, this produces far too many combinations.

排序和双指针利用有序性排除不可能的组合，将时间复杂度降低为 O(n²)。
Sorting and two pointers use ordering to eliminate impossible combinations, reducing the time complexity to O(n²).

易错点 / Common Pitfalls

• 必须对数组进行数值排序，即使用 .sort((a, b) => a - b)。
  Use numeric sorting with .sort((a, b) => a - b).
• 不仅要跳过固定元素 i 的重复值，找到答案后也要跳过 left 和 right 的重复值。
  Skip duplicates for the fixed index and for both pointers after finding a triplet.
• 去重应根据三元组的数值组合，而不是下标组合。
  Deduplicate by triplet values, not by index combinations.
• sorted[i] > 0 时可以停止，但 sorted[i] === 0 时仍需检查 [0,0,0]。
  Stop when sorted[i] > 0, but still process sorted[i] === 0 for [0,0,0].
• 三个元素必须来自不同下标；使用 i < left < right 可以自然保证这一点。
  The elements must come from distinct indices; i < left < right guarantees this naturally.
• 子问题是寻找两数之和等于 -sorted[i]，但实际比较完整三数之和通常更直观。
  The subproblem seeks two values summing to -sorted[i], though comparing the full triplet sum is often clearer.