Skip to main content

三数之和

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

简单做法：三层遍历，加hash储存去重，时间复杂度O（n^3）

双指针做法：排序后双指针的方法。具体步骤如下：

  1. 数组排序：首先对数组进行排序，便于后续去重和双指针操作。
  2. 遍历固定第一个元素：遍历数组，将当前元素作为三元组的第一个元素。
  3. 双指针查找剩余两个元素：在当前元素之后的子数组中使用双指针查找和为目标值（当前元素的相反数）的两个元素。
  4. 去重处理：跳过重复的元素，确保结果中没有重复的三元组。
function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

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

        const target = -nums[i];
        let left = i + 1;
        let right = n - 1;

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

            if (sum === target) {
                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 < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

代码解释：

  1. 排序：将数组排序后，相同元素会相邻，便于去重。
  2. 遍历固定第一个元素：遍历数组，对于每个元素 nums[i]，将目标值设为 -nums[i]。
  3. 双指针查找：在 i 之后的子数组中使用双指针 left 和 right 查找和为目标值的两个元素。
  4. 去重逻辑：
    • 跳过重复的第一个元素，避免重复的三元组。
    • 找到有效三元组后，跳过所有相邻的重复元素，确保结果唯一。

复杂度分析：

  • 时间复杂度：O(n²)，排序时间为 O(n log n)，双指针遍历时间为 O(n²)，总体复杂度由 O(n²) 主导。
  • 空间复杂度：O(log n)（排序栈空间）或 O(n)（取决于排序实现）。

三指针做法：先排序，再前后双指针加遍历中间数组，前后指针交替往中间移动，时间复杂度O（n^2）

  1. 排序数组：先对数组排序，便于去重和双指针操作。
  2. 固定中间指针 mid：遍历数组，将每个元素作为中间数。
  3. 左右双指针夹逼：
    • 左指针 left 从数组起点开始，但不超过 mid。
    • 右指针 right 从数组终点开始，必须在 mid 之后。
  4. 计算三数之和，根据和的大小调整指针位置。
function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let mid = 1; mid < n - 1; mid++) {
        // 跳过重复的中间数
        if (mid > 1 && nums[mid] === nums[mid - 1]) continue;

        let left = 0;
        let right = n - 1;
        const target = -nums[mid];

        while (left < mid && right > mid) {
            const sum = nums[left] + nums[right];

            if (sum === target) {
                result.push([nums[left], nums[mid], nums[right]]);
                // 跳过重复的左右数
                while (left < mid && nums[left] === nums[left + 1]) left++;
                while (right > mid && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}