1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// @Title: 三数之和 (3Sum)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 776 ms
// @Memory: 340.7 MB
import "sort"

/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和
 *
 * https://leetcode-cn.com/problems/3sum/description/
 *
 * algorithms
 * Medium (23.90%)
 * Likes:    1380
 * Dislikes: 0
 * Total Accepted:    97.4K
 * Total Submissions: 405.3K
 * Testcase Example:  '[-1,0,1,2,-1,-4]'
 *
 * 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0
 * ?找出所有满足条件且不重复的三元组。
 *
 * 注意:答案中不可以包含重复的三元组。
 *
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
 *
 * 满足要求的三元组集合为:
 * [
 * ⁠ [-1, 0, 1],
 * ⁠ [-1, -1, 2]
 * ]
 *
 *
 */

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

	res := make([][]int, 0, len(nums))

	// 1. 排序
	sort.Ints(nums)

	for i := range nums {
		// 注意i>0的判断条件
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		lo, hi := i+1, nLen-1 // 初始化双指针位置
		for lo < hi {
			sum := nums[i] + nums[lo] + nums[hi]
			// fmt.Println(nums, sum)
			if sum == 0 {
				res = append(res, []int{nums[i], nums[lo], nums[hi]})

				// 先做去重处理, lo<hi的条件带上, 防止边界溢出
				for lo < hi && nums[lo] == nums[lo+1] {
					lo++
				}
				for lo < hi && nums[hi] == nums[hi-1] {
					hi--
				}

				lo++
				hi--
			} else if sum < 0 {
				lo++
			} else if sum > 0 {
				hi--
			}
		}
	}

	return res

}