三数之和

难度：⭐⭐⭐ 面试超高频

考点

• 排序 + 双指针
• 去重处理
• 字节面试高频题

题目描述

给你一个整数数组 nums，找出所有和为 0 且不重复的三元组 [nums[i], nums[j], nums[k]]（i != j != k）。

函数签名

func threeSum(nums []int) [][]int

示例

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

输入：nums = [0,1,1]
输出：[]

输入：nums = [0,0,0]
输出：[[0,0,0]]

要求

1. 时间复杂度 O(n²)
2. 结果中不能有重复的三元组

提示

• 先排序，然后固定第一个数，用双指针找另外两个
• 去重：跳过与前一个相同的元素
• 剪枝：第一个数 > 0 时可以提前终止

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var result [][]int
	n := len(nums)

	for i := 0; i < n-2; i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i+1, n-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if sum < 0 {
				left++
			} else {
				right--
			}
		}
	}
	return result
}