三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 示例 2：

输入：nums = [] 输出：[] 示例 3：

输入：nums = [0] 输出：[]

解法一（暴力破解）：

import UIKit

var str = "Hello, playground"

var list = [-1,0,1,2,-1,-4]

let listLength = list.count
var result:[[Int]] = []
var sumStrings: [String] = []

for i in 0..<listLength - 2 {
    for j in (i + 1)..<listLength - 1 {
        for k in (j + 1)..<listLength {
            let sumArray = [list[i], list[j], list[k]].sorted()
            let sum = list[i] + list[j] + list[k]
            let sumString = sumArray.reduce("") { (result, current) -> String in
                return "\(result)\(current)"
            }

            if sum == 0 && !sumStrings.contains(sumString) {
                result.append([list[i], list[j], list[k]])
                sumStrings.append(sumString)
            }
        }
    }
}

print(result)

解法二：排序后双指针

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let listLength = nums.count
        var result:[[Int]] = []
        if listLength < 3 {
            return result
        }
        var list = nums.sorted() // 升序排序
        var sumStrings: [String] = []

        for i in 0..<listLength - 2 {
            var k = listLength - 1
            for j in (i + 1)..<listLength - 1 {
                var sum = list[i] + list[j] + list[k]
                while sum > 0 && k > j {
                    k -= 1
                    sum = list[i] + list[j] + list[k]
                }
                if k <= j {
                    break
                }
                let sumArray = [list[i], list[j], list[k]].sorted()
                let sumString = sumArray.reduce("") { (result, current) -> String in
                    return "\(result)\(current)"
                }
                if sum == 0 && !sumStrings.contains(sumString) {
                    result.append([list[i], list[j], list[k]])
                    sumStrings.append(sumString)
                }
            }
        }    

        return result
    }
}

上述解法的缺点是去重的判断上，需要用到额外的空间和字符串转换来判断。

解法三：基于解法二，优化去重的判断，重点在于数组已经排好序了。

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let listLength = nums.count
        var result:[[Int]] = []
        if listLength < 3 {
            return result
        }
        var list = nums.sorted() // 升序排序
        var sumStrings: [String] = []

        for i in 0..<listLength - 2 {
            if list[i] > 0 {
                break
            }
            // 去重
            if i > 0 && list[i] == list[i - 1] {
                continue
            }
            var k = listLength - 1
            for j in (i + 1)..<listLength - 1 {
                if list[j] + list[i] > 0 {
                    break
                }
                // 去重
                if j > (i + 1) && list[j] == list[j - 1] {
                    continue
                }
                var sum = list[i] + list[j] + list[k]
                while sum > 0 && k > j {
                    k -= 1
                    sum = list[i] + list[j] + list[k]
                }
                if k <= j {
                    break
                }
                if sum == 0 {
                    result.append([list[i], list[j], list[k]])
                }
            }
        }    

        return result
    }
}