一率触、題目原型：
給定一個包含 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.首先想到的最簡單最傻的做法是三層循環(huán)击狮，時間復雜度為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的我們統(tǒng)統(tǒng)不要了。我們需要拿到第一個負數生逸。
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]; // 這個就是動態(tà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;
}
// 如果兩個數字相同增炭，我們直接跳到下一個循環(huán)。
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()
// 如果兩個數字相同拧晕，我們直接跳到下一個循環(huán)。
while j < k && MutNums[j] == MutNums[j+1] {
j = j + 1
}
// 如果兩個數字相同梅垄，我們直接跳到下一個循環(huán)厂捞。
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.三層循環(huán) 347.76ms
2.滑尺優(yōu)化方案 2.64ms
話不多說靡馁，感受下這個天壤之別欲鹏。
四、小結
有任何疑問都可以留言臭墨，非常樂意一起探討赔嚎。??
個人博客地址
