leetcode_15. 三数之和

One minute read
LeetCode
面试 • 算法 • 数据结构

三数之和

题目

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：力扣（LeetCode）

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

思路

借用二元组，a = -(b+c)

即：遍历数组，从后面的集合里面找到两个数加起来是它的相反数，复杂度为O(n2)

注意剪枝和去重复

代码

func threeSum(nums []int) [][]int {
	if nums == nil || len(nums) < 3 {
		return nil
	}

	sort.Ints(nums)
	var ret [][]int
	for k, v := range nums {
		// 剪枝：排序后第一个字不可能大于0 || 后面还剩下一个数字
		if v > 0 || len(nums)-1-k <= 1 {
			break
		}

		if k > 0 && v == nums[k-1] { // 去重复
			continue
		}

		// 后面的集合里面找
		tmp := twoSUm(nums[k+1:], -v)
		if tmp != nil {
			for _, t := range tmp {
				// 先把满足条件的v塞入二元组，再把二元组塞入三元组
				ret = append(ret, append(t, v))
			}
		}
	}
	return ret
}

//求所有满足情况的二元组
func twoSUm(nums []int, target int) (ret [][]int) {
	var (
		m      = make(map[int]bool, len(nums))
		record = make(map[int]bool, len(nums))
	)

	for _, v := range nums {
		dif := target - v
		// map内包含符合条件的 target-v && 去重复([1,2] [2,1])
		if m[dif] && !record[v] {
			ret = append(ret, []int{v, dif})
			record[v] = true //标记重复
		} else {
			m[v] = true // 标记暂不符合条件的值
		}
	}
	return
}

分享：