15. 3Sum

15. 3Sumopen in new window

🟠 🔖 数组 双指针 排序 🔗 LeetCodeopen in new window

题目

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

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
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.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

解题思路

这一题比较麻烦的一点在于，最后输出解的时候，要求输出不重复的解。
数组中同一个数字可能出现多次，同一个数字也可能使用多次，但是最后输出解的时候，不能重复。例如 [-1, -1, 2] 和 [2, -1, -1]、[-1, 2, -1] 这 3 个解是重复的。
这就需要排序和去重，使用对撞指针寻找三数之和为 0 的组合。
先对数组进行排序，i 从后往前扫描，这里同样需要注意数组中存在多个重复数字的问题。i 在循环的时候和后一个数进行比较，如果相等，i 继续往前移，直到移到下一个和前一个数字不同的位置。
j，k 两个指针开始一前一后对撞。j 从数组首位开始，k 为 i 的前一个数字，由于经过排序，所以 j < k。对比三个数的和与 target 的大小，小于 target，j 往后移动；大于 target，k 往前移动，寻找三数之和为 target 的组合，移动指针时注意去重。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums = nums.sort((a, b) => a - b);
  const target = 0;
  let res = [];
  for (let i = nums.length - 1; i > 1; i--) {
    // 排除 i 重复的情况
    if (i === nums.length - 1 || nums[i] != nums[i + 1]) {
      let j = 0;
      let k = i - 1;
      let sum = target - nums[i];
      while (j < k) {
        if (nums[j] + nums[k] === sum) {
          res.push([nums[i], nums[j], nums[k]]);
          // 排除 j 重复的情况
          while (j < k && nums[j] === nums[j + 1]) {
            j++;
          }
          // 排除 k 重复的情况
          while (j < k && nums[k] === nums[k - 1]) {
            k--;
          }
          j++;
          k--;
        } else if (nums[j] + nums[k] < sum) {
          j++;
        } else {
          k--;
        }
      }
    }
  }
  return res;
};

15. 3Sum

# 15. 3Sumopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

15. 3Sumopen in new window

题目

题目大意

解题思路

代码

相关题目