Pengjielee's blog

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

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

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

提示：

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let result = [];
  // 传入数组为null直接返回result
  if (nums === null) {
    return result;
  }

  const len = nums.length;
  // 传入数组长度小于3直接返回result
  if (len < 3) {
    return result;
  }

  // 对传入数组进行排序
  nums.sort((a, b) => a - b);

  for (let i = 0; i < len; i++) {
    // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
    if (nums[i] > 0) {
      break;
    } 
    // 确保nums[i]改变了
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    } 
    //左指针
    let start = i + 1;
    //右指针
    let end = len - 1;

    //固定一个数
    while (start < end) {
      const sum = nums[i] + nums[start] + nums[end];
      if (sum == 0) {
        result.push([nums[i], nums[start], nums[end]]);
        // 确保nums[start]改变了
        while (start < end && nums[start] === nums[start + 1]) {
          start++;
        }
        // 确保nums[end]改变了
        while (start < end && nums[end] === nums[end - 1]) {
          end--;
        }
        start++;
        end--;
      } else if (sum < 0) {
        // 三数之和 < 0，start++
        start++;
      } else if (sum > 0) {
        // 三数之和 > 0，end--
        end--;
      }
    }
  }
  return result;
};

Go实现

package main

import (
  "fmt"
  "sort"
)

func main() {
  fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
}

func threeSum(nums []int) [][]int {
  sort.Ints(nums)
  var result [][]int

  for i := 0; i < len(nums)-2; i++ {
    // 剪枝：最小值大于0时无需再遍历
    if nums[i] > 0 {
      break
    }
    // 剪枝：最小值和前一个值一样时，上一个循环已经判断过，无需再判断
    if i > 0 && nums[i] == nums[i-1] {
      continue
    }
    // j,k 为两个指针，分别从最左边和最右边开始移动
    j, k := i+1, len(nums)-1
    for j < k {
      left, right := nums[j], nums[k]
      if nums[i]+nums[j]+nums[k] == 0 {
        result = append(result, []int{nums[i], nums[j], nums[k]})
        // 减枝：跳过 nums[j] == nums[j+1] 的情况
        for j < k && nums[j] == left {
          j++
        }
        // 减枝：跳过 nums[k] == nums[k-1] 的情况
        for j < k && nums[k] == right {
          k--
        }
      } else if nums[i]+nums[j]+nums[k] < 0 {
        // 和小于0，则增大最左边的j
        j++
      } else {
        // 和大于0，则减少最右边的k
        k--
      }
    }
  }
  return result
}