给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
暴力解法
三次循环
时间复杂度为O(n^3)
空间复杂度为o(n)，排序之后的数组
提交LeetCode失败，提示超时
*/
func threeSum(_ nums: [Int]) -> [[Int]] {
// Set 集合去重
var set = Set<[Int]>()
guard nums.count > 2 else {
return Array(set)
}
let sortedNums = nums.sorted { (n1, n2) -> Bool in
n1 < n2
}
for i in 0..<sortedNums.count {
for j in (i+1)..<sortedNums.count {
for k in (j+1)..<sortedNums.count {
if sortedNums[i] + sortedNums[j] + sortedNums[k] == 0 {
let list = [sortedNums[i], sortedNums[j], sortedNums[k]]
set.insert(list)
}
}
}
}
return Array(set)
}
/**
双指针
三数之和，a + b + c = 0
先排序数组
拆解 a + b = -c，假设第一个数就是-c，变成了求两数之和
使用双指针，一个在头部，一个在尾部，向中间靠拢确定出 a 和 b
时间复杂度为O(n^2)
空间复杂度为O(n) 排序后使用另外的数组保存
执行结果：通过
执行用时：264 ms, 在所有 Swift 提交中击败了77.39%的用户
内存消耗：23.4 MB, 在所有 Swift 提交中击败了100.00%的用户
*/
func threeSum(_ nums: [Int]) -> [[Int]] {
var result = [[Int]]()
// 过滤数据
guard nums.count > 2 else {
return result
}
// 排序
let sortedNums = nums.sorted { (n1, n2) -> Bool in
n1 < n2
}
for i in 0..<sortedNums.count {
if sortedNums[i] > 0 {
break
}
// 去重
if i > 0 && sortedNums[i] == sortedNums[i-1] {
continue
}
// 假设第一个值为 目标值，之后进行两数之和计算，头尾双指针
let target = -sortedNums[i]
var left = i + 1
var right = sortedNums.count-1
while left < right {
if sortedNums[left] + sortedNums[right] == target {
let list = [sortedNums[i], sortedNums[left], sortedNums[right]]
result.append(list)
// 去除头部重复数据
while left < right && sortedNums[left] == sortedNums[left+1] {
left += 1
}
// 去除尾部重复数据
while left < right && sortedNums[right] == sortedNums[right-1] {
right -= 1
}
left += 1
right -= 1
} else if(sortedNums[left] + sortedNums[right] < target) {
left += 1
} else {
right -= 1
}
}
}
return result
}
/**
结合LeetCode上的其他朋友的提交记录进一步优化一些细节
执行时间比上一个代码减少一些
执行结果：通过
执行用时：248 ms, 在所有 Swift 提交中击败了93.97%的用户
内存消耗：23.8 MB, 在所有 Swift 提交中击败了52.17%的用户
*/
func threeSum(_ nums: [Int]) -> [[Int]] {
var result = [[Int]]()
// 过滤数据
guard nums.count > 2 else {
return result
}
// 升序 排序
let sortedNums = nums.sorted { (n1, n2) -> Bool in
n1 < n2
}
// 遍历的最后节点从 count -> count-2 ，
// i, left=i+1, right=count-1 这种状态才需要处理
// i=count-1, left=count, right=count，left==count 无需在遍历中处理，直接在此过滤掉
for i in 0..<sortedNums.count-2 {
// 排序之后，第一个数大于0，之后全部大于0，没有满足条件的数据
if sortedNums[i] > 0 {
break
}
// 去重
if i > 0 && sortedNums[i] == sortedNums[i-1] {
continue
}
// 假设第一个值为 目标值，之后进行两数之和计算，头尾双指针
let target = -sortedNums[i]
var left = i + 1
var right = sortedNums.count-1
while left < right {
if sortedNums[left] + sortedNums[right] == target {
let list = [sortedNums[i], sortedNums[left], sortedNums[right]]
result.append(list)
// 去除头部重复数据
while left < right && sortedNums[left] == sortedNums[left+1] {
left += 1
}
// 去除尾部重复数据
while left < right && sortedNums[right] == sortedNums[right-1] {
right -= 1
}
left += 1
right -= 1
} else if(sortedNums[left] + sortedNums[right] < target) {
left += 1
} else {
right -= 1
}
}
}
return result
}
let nums = [-1,0,1,2,-1,-4]
threeSum(nums)
