描述：
给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0 ？找出所有满足条件且不重复的三元组
注意：答案中不可以包含重复的三元组
例：给定数组 nums=[-1, 0, 1, 2, -1, -4]
满足要求的三元集合为：[[-1, 0, 1], [-1, -1, 2]]
一、暴力法
思路：数组先从小到大的顺序排序，然后遍历数组，取3个数判断它们的和是否等于0，存储组合是，判断该组合是否存储过，目的是去重
时间复杂度：O(n^3)
具体实现：
func threeSum(_ nums: [Int]) -> [[Int]] { if nums.count == 0 { return [] } let nums = nums.sorted { (a, b) -> Bool in return a < b } var array : [[Int]]! = [[Int]]() for i in 0..<nums.count-2 { let a = nums[i] var j = i+1 while j < nums.count-1{ let b = nums[j] var k = j+1 while k < nums.count{ let c = nums[k] if a+b+c == 0{ let arr = [a,b,c] //去重：看结果数组中是否已经包含该组合，若包含则继续往下，若不包含，则加入结果数组 if !array.contains(arr){ array.append(arr) } } k = k+1 } j = j+1 } } return array }
二、双指针法
思路：固定一个值，找另外二个值它们和等于 0，这两个数的寻找利用双指针，左指针指向1，右指针指向最后一个数，依次向中间遍历
时间复杂度：O(nlog(n))
具体实现：
/* 固定一个值，找另外二个值它们和等于 0， 如何找另外两个值，用的是双指针！ */ func threeSum(_ nums: [Int]) -> [[Int]] { if nums.count == 0 { return [] } let nums = nums.sorted { (a, b) -> Bool in return a < b } let len = nums.count var array : [[Int]] = [[Int]]() for i in 0..<len { if i>0 && nums[i] == nums[i-1] { continue } var left = i+1 var right = len-1 while left < right { let tmp = nums[i]+nums[left]+nums[right] //判断三个数的和是否等于0 if tmp==0 { array.append([nums[i], nums[left], nums[right]]) //当左指针的数等于其后一个数时，左指针往右移一位 //其目的是：去除重复的数 while left<right && nums[left]==nums[left+1]{ left = left+1 } //当右指针的数等于其前一个数时，右指针往左移一位 while left<right && nums[right]==nums[right-1]{ right = right-1 } left = left+1 right = right-1 }else if tmp>0 { //三数之和>0时，将右指针往左移一位 right = right - 1 }else{ //三数之和<0时，将左指针往右移一位 left = left+1 } } } return array }
