38. [中等] 三数之和

# 出题内容

给你一个包含 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
- -105 <= nums[i] <= 105

# 代码参考

```go
// 参考示例1（推荐）
package main

import (
	"fmt"
	"sort"
)

func threeSum(nums []int) [][]int {
	sort.Ints(nums) // 对数组进行排序
	result := [][]int{}

for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue // 跳过重复的元素
		}

left := i + 1
		right := len(nums) - 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
}

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

```go
// 参考示例2（不推荐）
package main

import (
	"fmt"
	"sort"
)

func threeSum(any []int) [][]int {

res := [][]int{}
	sort.Ints(any)

for i := 0; i < len(any); i++ {
		for j := i + 1; j < len(any); j++ {
			for k := j + 1; k < len(any); k++ {
				if i > 0 && any[i] == any[i-1] {
					continue
				}
				if any[i]+any[j]+any[k] == 0 {
					res = append(res, []int{any[i], any[j], any[k]})
				}
			}
		}
	}

return res
}

func main() {
	arr := []int{-1, 0, 1, 2, -1, -4}

fmt.Println(threeSum(arr))
}
```

# 代码原理
使用双指针法来找到和为零的三元组。

1. 首先，我们对数组进行排序，然后遍历数组中的每个元素。

2. 对于当前遍历到的元素 nums[i]，使用两个指针，一个指针指向 i 的下一个元素 nums[left]，另一个指针指向数组的最后一个元素 nums[right]。计算三个元素的和 sum = nums[i] + nums[left] + nums[right]。

2.1. 如果 sum 等于零，我们就找到了一个和为零的三元组，将它添加到结果列表中。然后，我们将 left 指针右移一位，right 指针左移一位，以继续寻找下一个可能的三元组。

2.2. 如果 sum 大于零，说明右侧的元素太大，需要将 right 指针左移一位，以减小 sum 的值。

2.3. 如果 sum 小于零，说明左侧的元素太小，需要将 left 指针右移一位，以增大 sum 的值。

3. 在遍历过程中，我们还要注意跳过重复的元素，以避免得到重复的三元组。当我们找到一个和为零的三元组后，我们需要继续移动指针，直到指向不同的元素为止。

# 输出结果
```
[[-1 -1 2] [-1 0 1]]
```