暴力求解思路

刚开始看到题目的想法就是暴力求解，锚定前两个元素，根据结果确定第三个元素，就是三层 while 循环。

代码如下所示：

var i = 0; var j = 0; var k = 0;
var res = [[Int]]()
while i < nums.count {
    j = i + 1
    while j < nums.count {
        k = j + 1
        while k < nums.count {
            if nums[i] + nums[j] + nums[k] == 0 {
                res.append([nums[i], nums[j], nums[k]])
            }
            k = k + 1
        }
        j = j + 1
    }
    i = i + 1
}

但是有个问题是元素内容不能重复，像下面这种 case 中，输出结果的第零个和第二个元素是重复的

输入:[-1,0,1,2,-1,-4]
输出: [[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]

我们想办法通过 Set 的方式去过滤结果中的元素，代码如下

static func threeSum(_ nums: [Int]) -> [[Int]] {
    var i = 0; var j = 0; var k = 0;
    var res = [[Int]]()
    while i < nums.count {
        j = i + 1
        while j < nums.count {
            k = j + 1
            while k < nums.count {
                if nums[i] + nums[j] + nums[k] == 0 {
                    res.append([nums[i], nums[j], nums[k]])
                }
                k = k + 1
            }
            j = j + 1
        }
        i = i + 1
    }
    var set = Set<[Int]>()
    for re in res { set.insert(re.sorted()) }
    return Array.init(set)
}

执行结果能满足要求，但是时间复杂度很高 O(n^3)… 所以提交后报超出限制..

哈希解法

参考卡哥的解法 (opens new window)，确定前两个值之后，然后通过哈希表查找第三个值，这么做的时间复杂度是 O(n^2)，找到的话就放到数组中。至于最后过滤解法的过程，直接通过 Set 帮忙过滤了。

这个解法其实和两数之和的思路还是挺像的，都是借助了哈希去进行 O(1) 时间复杂度的查找，最终能够通过测试，但是时间还是挺长的..

func threeSum(_ nums: [Int]) -> [[Int]] {
    var i = 0; var j = 0; var k = 0;
    var dict = [Int:Int]()
    for (index,num) in nums.enumerated() {
        dict[num] = index
    }
    var res = [[Int]]()
    while i < nums.count {
        j = i + 1
        while j < nums.count {
            let t = 0 - nums[i] - nums[j]
            if let index = dict[t], index != i, index != j {
                res.append([nums[i], nums[j], t])
            }
            j = j + 1
        }
        i = i + 1
    }
    var resSet = Set<[Int]>()
    for re in res { resSet.insert(re.sorted()) }
    return Array.init(resSet)
}

排序+暴力解法

有没有更快的解法，看了官方题解后，发现题解为了减少运算的时间复杂度，官方题解先对输入数组做了从小到大排序。

如果排序后的前三个元素加起来大于0，则后面的压根也不用遍历了，因为结果只会更大。

如果沿用之前的暴力求解法则，其实也能减少暴力遍历的次数，代码大致如下

static func threeSum(_ nums: [Int]) -> [[Int]] {
    var i = 0; var j = 0; var k = 0;
    var sortNums = nums.sorted()
    var res = [[Int]]()
    while i < sortNums.count {
        j = i + 1
        while j < sortNums.count {
            if sortNums[i] + sortNums[j] > 0 { break }
            k = j + 1
            while k < sortNums.count {
                if sortNums[i] + sortNums[j] + sortNums[k] == 0 {
                    res.append([sortNums[i], sortNums[j], sortNums[k]])
										break
                } else if sortNums[i] + sortNums[j] + sortNums[k] > 0 {
                    break
                } else {
                    k = k + 1
                }
            }
            j = j + 1
        }
        i = i + 1
    }
    var set = Set<[Int]>()
    for re in res { set.insert(re.sorted()) }
    return Array.init(set)
}

但是遇到极端情况还是比如无论如何加都小于0，则最差的情况还是时间复杂度为 O(n^3)

排序+双指针（官方题解）

为了避免「额外的去重消耗」以及「减少遍历次数」，所以尝试使用最终的排序后双指针遍历的方法。

总体思路是采用一个游标指针，然后配合游标指针对应的两个左右指针去遍历，左指针指向游标的下一个元素，右指针指向数组最后的元素，然后依次向中间靠拢，在遍历过程中直接进行去重操作。

代码如下

static func threeSum(_ nums: [Int]) -> [[Int]] {
    var i = 0, left = 0, right = 0
    var res = [[Int]]()
    let sortedNums = nums.sorted()
    while i < sortedNums.count {
        left = i + 1
        right = sortedNums.count - 1
        if sortedNums[i] > 0 { break }
        if i > 0 && sortedNums[i] == sortedNums[i-1] {
            i = i + 1
            continue
        }
        while right > left {
            if sortedNums[i] + sortedNums[left] + sortedNums[right] == 0 {
                res.append([sortedNums[i], sortedNums[left], sortedNums[right]])
                while right > left, sortedNums[right] == sortedNums[right-1] {
                    right = right - 1
                }
                while right > left, sortedNums[left] == sortedNums[left+1] {
                    left = left + 1
                }
                left = left + 1
                right = right - 1
            } else if sortedNums[i] + sortedNums[left] + sortedNums[right] > 0 {
                right = right - 1
            } else {
                left = left + 1
            }
        }
        i = i + 1
    }
    return res
}

这里面有个去重操作需要注意一下，就是下面这行代码比较容易写错，错误的写法会使得 [-1,-1,2] 这种case不会被计算到最终结果里。

✅ if i > 0 && sortedNums[i] == sortedNums[i-1]  
❎ if sortedNums[i] == sortedNums[i+1]

我最开始没有想明白为什么 == 0 之后，双指针要同时收缩，想了下其实也很好理解，如果只有一边另一边不收缩的话，所以是两边需要同时收缩。

• 只移动右边指针，最后得到的结果一定是小于 0 的
• 只移动左边指针，最后得到的结果一定是大于 0 的

其他都比较好理解。我自己感觉双指针这种方法对于遍历过程中比较细粒度的控制（根据某种条件判断下标的修改）还挺有效的。