LeetCode 15. 三数之和 3sum

【题目描述】
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

【示例】

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

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

【思路】
1、使用双指针
2、因为要三者相加等于0，那么首先想到的是要对数组排序
3、正因为排好序后 左右指针才好一一对应起来，想要的状态就是：

• 左边小于0
• 右边大于0
• 中间等于0
  4、这样左右指针移动才可以相互抵消，最终达到三者之和为0
  5、要注意去重
  6、左右指针走到中间且不相等，遍历结束
  7、时间复杂度O(nlogn)
  8、空间复杂度O(n)

Swift代码实现：

func threeSum(_ nums: [Int]) -> [[Int]] {
    var res = [[Int]]()
    var tmp = nums.sorted()
    for k in 0..<tmp.count {
        if k>0 && tmp[k] == tmp[k-1] {//去重
            continue
        }
        var r = tmp.count-1
        var l = k+1
        while l < r {
            if tmp[k] > 0 {
                return res
            }
            let value = tmp[k]+tmp[l]+tmp[r]
            if value > 0 {
                r-=1
            } else if value < 0 {
                l+=1
            } else {
                while l<r && tmp[l] == tmp[l+1] {//去重
                    l+=1
                }
                while l<r && tmp[r] == tmp[r-1] {
                    r-=1
                }
                res.append([tmp[k],tmp[l],tmp[r]])
                l+=1
                r-=1
            }
        }
    }
    return res
}