• 题目描述

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

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

    ​ 示例：

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

    满足要求的三元组集合为：

    1
    2
    3
    4
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

  • 解题说明

    • 将数组进行排序，从左向右依次从小到大进行排序；

    • 判断数组长度是否满足输入，如果长度小于等于2，则返回空数组；

    • 定位找值，先固定一个数值，然后定义两个指针，进行左右移动进行目标值确定。如果三个数和等于0，则将三个数加入到结果数组中，在进行判重，如果左指针的值等于左指针加一的值，即相邻数相等，则左指针继续加一，判重条件为左指针小于右指针，退出循环。退出循环后，左右指针各加一，继续从中间向两边查找。如果计算结果大于0，则右指针左移，否则左指针右移。

    指针移动

  • 代码实例

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
package main

import (
	"fmt"
	"sort"
)

/*
@Time    : 2020/8/29 19:59
@Author  : austsxk
@Email   : austsxk@163.com
@File    : day1_threeNumberSum.go
@Software: GoLand
*/

func threeSum(nums []int) [][]int {
	// 将数组进行从小到大的排序
	sort.Ints(nums)
	if len(nums) <= 2 {
		return [][]int{}
	}
	var result [][]int
	var left, right = 0, 0
	for i := 0; i < len(nums); i ++ {
		// 如果最左侧的值大于0,则后面的值加起来肯定超过0，直接退出循环
		if nums[i] > 0 {
			break
		}
		// 如果连续数值相同，则直接进行下一个
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		left = i + 1
		right = len(nums) - 1
		for left < right {
			data := nums[i] + nums[left] + nums[right]
			// 如果正好等于0，则左右都移动，向中间逼近，并进行判重
			if data == 0 {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				// 此处去重复，如果从左侧连着一样，直接去除掉
				for left < right {
					if nums[left] == nums[left+1] {
						left ++
					} else {
						break
					}
				}
				// 判断去重复后，直接左右向中间移动
				left ++
				right --
			}
			// 如果小于0，则说明左侧值偏小，则左指针右移动
			if data < 0 {
				left ++
			}
			// 如果大于0，说明右侧值偏大，则指针左移动
			if data > 0 {
				right --
			}
		}
	}
	return result
}

func main() {
	var testList []int = []int{-1,0,1,2,-1,-4}
	d := threeSum(testList)
	fmt.Println(d)
}