一、题目原型：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
二、题目意思剖析：
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1], [-1, -1, 2]]
三、解题思路：
3.1.首先想到的最简单最傻的做法是三层循环，时间复杂度为O(n的三次方)。。。想想都觉得耗时。。。非常不建议，只是一个思路而已。
func threeSum(_ nums: [Int]) -> [[Int]] {
var newNums: [Int] = []
var haha:[[Int]] = []
for i in 0..<nums.count {
for j in i+1..<nums.count {
for k in j+1..<nums.count {
if nums[i] + nums[j] + nums[k] == 0 {
newNums.append(nums[i])
newNums.append(nums[j])
newNums.append(nums[k])
newNums.sort()
if haha.contains(newNums) {
newNums.removeAll()
continue
}
haha.append(newNums)
}
newNums.removeAll()
}
}
}
return haha
}
3.2.经过耗时太长的惨痛经历，痛定思痛，我觉得从题目“三数之和=0”入手。排除三个数都为0的情况，也就是[0,0,0]；请他情况必定是有一个负数的。所以我们可以首先就排个序。
//第一步：排序
比如刚开始是[-1, 0, 1, 2, -1, -4]
排序后变成是[-4, -1, -1, 0, 1, 2]
排序完，是不是觉得思路有了，对的。我们只需要遍历前面的负数和0，也就是>0的我们统统不要了。我们需要拿到第一个负数。
for i in 0..<MutNums.count {
if (MutNums[i] > 0) {
break;
}
// MutNums[i]就是一个负数
}
拿到第一个负数后，我们只需要再拿到后面两个数，与之相加=0即可。后面两个数我们用两个指针来表示，j和k，一个是从左边往右边走，一个是从最右边往前走。有些思想就是想通的，之前的两数之和就是这种思路。先排好序，左边一个left指针，右边一个right指针，如果left+right > result，那么right往左移，如果left+right < result，那么说明相加得数不够，就需要left往右移。找到相加之和相等的就行。此题，也是如此。
let target = 0 - MutNums[i]; // 这个就是动态的reslut
var j = i+1, k = MutNums.count - 1
if (MutNums[j] + MutNums[k] == target) {
//这就回到了两数之和那个简单的问题。
}
不过在这里要注意一个问题，就是题目中提到的“答案中不可以包含重复的三元组”，所以我们需要把相同的数字过滤掉。
其实很简单，只需要往下或者往前走一位，其他什么都不要做。
while j < k && MutNums[j] == MutNums[j+1] {
j = j + 1
}
贴出代码
func threeSum(_ nums: [Int]) -> [[Int]] {
var MutNums: [Int] = nums
var newNums: [Int] = []
var haha:[[Int]] = []
// 1.排序 对于MutNums[i]来说，我们只需要负数和0，因为三个数之和为0，一定是有一个数为负数的，当然除去三个数都为0的情况。所以，我们取非正数。
MutNums.sort()
for i in 0..<MutNums.count {
if (MutNums[i] > 0) {
break;
}
// 如果两个数字相同，我们直接跳到下一个循环。
if (i > 0 && MutNums[i] == MutNums[i-1]) {
continue
}
let target = 0 - MutNums[i];
var j = i+1, k = MutNums.count - 1
while j < k {
// 2.找到后面的两个与MutNums[i]对应的数字
if (MutNums[j] + MutNums[k] == target) {
newNums.append(MutNums[i])
newNums.append(MutNums[j])
newNums.append(MutNums[k])
haha.append(newNums)
newNums.removeAll()
// 如果两个数字相同，我们直接跳到下一个循环。
while j < k && MutNums[j] == MutNums[j+1] {
j = j + 1
}
// 如果两个数字相同，我们直接跳到下一个循环。
while j < k && MutNums[k] == MutNums[k-1] {
k = k - 1
}
// 否则就往中间靠拢
j = j + 1;k = k - 1
}else if (MutNums[j] + MutNums[k] < target) {
// 如果后面两数相加小于target，说明左边还得往右移
j = j + 1
}else {
// 如果后面两数相加大于target，说明右边就要往左移
k = k - 1
}
}
}
return haha
}
运行数组
[13,9,1,12,-7,-12,7,3,9,6,-7,4,9,5,5,-7,4,11,1,-2,12,3,-12,-15,0,-12,-6,-1,7,-5,-4,-3,12,4,-14,-10,-1,8,1,-6,-1,9,13,-14,-1,-5,-6,-12,-8,2,2,11,13,-3,11,-2,1,-10,4,-15,-8,7,-11,11,-4,-10,-13,3,5,3,12,11,-11,2,12,3,13,13,-2,12,-7,-15,8,-9,-10,-4,-4,6,1,-15,-2,0,-1,2,-3,10,-1,-9,-10,-11,1,-13,-15,5,-3,5,-7,-5,-5,6,14,3,-1,7,1,-4,-12,12,-13,-4,4,0,3,-12,9,-15,6]
耗时对比：
1.三层循环 347.76ms
2.滑尺优化方案 2.64ms
话不多说，感受下这个天壤之别。
四、小结
总提交数
提交结果
有任何疑问都可以留言，非常乐意一起探讨。😄
个人博客地址
