题目描述：

  1. 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
  3. 注意：答案中不可以包含重复的三元组。
  7. 示例 1：
  9. 输入：nums = [-1,0,1,2,-1,-4]
  10. 输出：[[-1,-1,2],[-1,0,1]]
  11. 示例 2：
  13. 输入：nums = []
  14. 输出：[]
  15. 示例 3：
  17. 输入：nums = [0]
  18. 输出：[]
  21. 提示：
  23. 0 <= nums.length <= 3000
  24. -105 <= nums[i] <= 105

思路：

根据题意，获取三个数之和为0，实质上就是对给出的数组进行全排列，然后选出结果等于0的，再去掉重复的。题目中给出的nums的长度范围是0-3000，由此可以猜测，这道题的时间复杂度最多就O(n^2)，如果用三重循环去暴力解答 ，那肯定会超时。
去重
对于去重的操作，可以使用哈希表，这样做需要找出所有结果为0的集合，并且使用哈希表存储，时间复杂度和空间复杂度都比较高。因此可以考虑对原数组进行排序，然后固定三个数中的其中一个，另外两个数使用双指针来进行去重的操作，如果两个相邻的数相同，那就可以将指针前移或者后移。
固定第一个数比较简单，同样的套路可应用于最接近的三数之和以及四数之和。

  1. /*
  2.  * @lc app=leetcode.cn id=15 lang=golang
  3.  *
  4.  * [15] 三数之和
  5.  */
  7. // @lc code=start
  8. func threeSum(nums []int) [][]int {
  9.     quickSort(nums)
  10.     var buf [][]int
  11.     for i := 0; i < len(nums); i++ {
  12.         if i > 0 && nums[i] == nums[i-1] {
  13.             continue
  14.         }
  16.         start, end := i+1, len(nums)-1//固定第一个数
  17.         for start < end {
  18.             if start > i+1 && start < len(nums) && nums[start] == nums[start-1] {
  19.                 start++
  20.                 continue
  21.             }
  22.             if end < len(nums)-1 && end >= start && nums[end] == nums[end+1] {
  23.                 end--
  24.                 continue
  25.             }
  26.             if nums[i]+nums[start]+nums[end] > 0 {
  27.                 end--
  28.             } else if nums[i]+nums[start]+nums[end] < 0 {
  29.                 start++
  30.             } else {
  31.                 buf = append(buf, []int{nums[i], nums[start], nums[end]})
  32.                 start++
  33.                 end--
  34.             }
  35.         }
  36.     }
  38.     return buf
  39. }
  41. func quickSort(nums []int) {
  42.     if len(nums) < 2 {
  43.         return
  44.     }
  45.     head, tail := 0, len(nums)-1
  46.     reference := nums[0]
  47.     i := 1
  48.     for head < tail {
  49.         if nums[i] < reference {
  50.             nums[head], nums[i] = nums[i], nums[head]
  51.             head++
  52.             i++ //这里的i已经进行过自增了，在else里面就不需要了，快速排序不用遍历完整个数组
  53.         } else {
  54.             nums[tail], nums[i] = nums[i], nums[tail]
  55.             tail--
  56.         }
  57.     }
  58.     quickSort(nums[:head])
  59.     quickSort(nums[head+1:])
  60. }
  62. // @lc code=end

排序是自己写的快排，其实可以使用官方的sort包来进行处理，这样写只是为了复习。。。
LeetCode