题目

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Swift解法

class Solution {
        var values = [Int]()
        var answers = [[Int]]()
        func index(of value: Int, from: Int, to: Int) -> Int {
            let middle = (from + to) / 2
            if values[middle] == value {
                return middle
            } else if values[middle] < value {
                if middle + 1 <= to {
                    return index(of: value, from: middle + 1, to: to)
                } else {
                    return -1
                }
            } else if values[middle] > value {
                if middle - 1 >= from {
                    return index(of: value, from: from, to: middle - 1)
                } else {
                    return -1
                }
            }
            return -1
        }
        
        func threeSum(_ nums: [Int]) -> [[Int]] {
            self.values.removeAll()
            let vals = nums.sorted()
            var lastValue: Int?
            var repeatCount = 0
            for i in 0..<vals.count {
                let current = vals[i]
                if lastValue != current {
                    lastValue = current
                    repeatCount = 0
                } else {
                    repeatCount += 1
                }
                if repeatCount <= 1 || (repeatCount == 2 && lastValue == 0) {
                    self.values.append(current)
                }
            }
            var answers = [[Int]]()
            var i = 0
            var j = 0
            var flag = [String: Bool]()
            while i < values.count - 2 {
                var total = 0
                total += values[i]
                if total > 0 {
                    break
                }
                j = i + 1
                while j < values.count - 1 {
                    var total = total
                    total += values[j]
                    if total > 0 {
                        break
                    }
                    let k = index(of: -total, from: j + 1, to: values.count - 1)
                    if k != -1 {
                        let key = [values[i].description, values[j].description, values[k].description].joined(separator: "_")
                        if !flag.keys.contains(key) {
                            flag[key] = true
                            answers.append([values[i], values[j], values[k]])
                        }
                    }
                    j += 1
                }
                i += 1
            }
            return answers
        }
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。