一、题目原型：

给定一个包含 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
话不多说，感受下这个天壤之别。

四、小结

总提交数 提交结果

有任何疑问都可以留言，非常乐意一起探讨。😄