三数之和

题目

给你一个包含 n 个整数的数组 nums, 判断是否存在三个元素 a, b, c, 使得 a + b + c = 0, 找出这样满足条件且不重复的所有三元组.

提示:

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

示例

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

输出: [[-1, 0, 1], [-1, -1, 2]]

题解

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // Sort the array
  nums.sort((a, b) => a - b)
  const result = []
  const n = nums.length

  for (let i = 0; i < n - 2; i++) {
    // Skip duplicate values for i
    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) {
        // Found a triplet
        result.push([nums[i], nums[left], nums[right]])

        // Skip duplicate values for left and 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
}

Rust

pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut nums = nums;
    nums.sort();
    let mut result: Vec<Vec<i32>> = vec![];

    for i in 0..(n - 2) {
        if i > 0 && nums[i] == nums[i - 1] {
            continue;
        }

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

        while left < right {
            let sum = nums[i] + nums[left] + nums[right];

            if sum < 0 {
                left += 1;
            }

            if sum > 0 {
                right -= 1;
            }

            if sum == 0 {
                result.push(([nums[i], nums[left], nums[right]].to_vec()));

                while left < right && nums[left] == nums[left + 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right - 1] {
                    right -= 1;
                }

                left += 1;
                right -= 1;
            }
        }
    }

    result
}