三数之和

# 题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

# 思考

首先想到的解决方案是暴力，写三层for循环，这样便可以获取到所有可能的结果，但是题目要求结果不重复，结果无序处理不重复相对麻烦；题目类型是关于双指针的，通常需要从两边开始向中间夹逼，没有思路题解采用固定左端点，然后左右指针进行遍历，至于不重复问题，将数组排序后，重复端点只遍历一次，即可解决，时间复杂度为O(N^2)，空间复杂为O(1)。

# 代码

 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


package main

import (
	"fmt"
	"sort"
)

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

func threeSum(nums []int) [][]int {
	ans := make([][]int, 0)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] <= nums[j]
	})
	for k := 0; k < len(nums); k++ {
		if nums[k] > 0 {
			break
		}
		if k > 0 && nums[k] == nums[k-1] {
			continue
		}
		i, j := k+1, len(nums)-1
		for i < j {
			sum := nums[k] + nums[i] + nums[j]
			if sum == 0 {
				ans = append(ans, []int{nums[k], nums[i], nums[j]})
				for i < j && nums[i] == nums[i+1] {
					i++
				}
				for i < j && nums[j] == nums[j-1] {
					j--
				}
				i, j = i+1, j-1
			} else if sum < 0 {
				i++
			} else {
				j--
			}
		}
	}
	return ans
}

# 延伸

在数组中找出任意两个数和为0

排序后，使用双指针从两端遍历，遇到相等的跳过。

在数组中找出任意四个数和为0

固定左右端点即可？