8.LeetCode刷题For Swift·15. 3Sum 三

1、原题

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

2、思路

3、代码

func threeSum(_ nums: [Int]) -> [[Int]] {
    // 先排序
    let newNums = nums.sorted()
    // 返回结果数组
    var result = [[Int]]()
    for i in 0..<newNums.count {
        // 排序之后如果第一个元素已经大于零
        if newNums[i] > 0 {
            return result
        }
        // 去重
        if i > 0 && newNums[i] == newNums[i - 1] {
            continue
        }
//        if newNums[i] == newNums[i + 1] {
//            continue
//        }
        var left = i + 1
        var right = newNums.count - 1
        while left < right {
            if (newNums[i] + newNums[left] + newNums[right]) > 0 {
                right -= 1
            } else if (newNums[i] + newNums[left] + newNums[right]) < 0 {
                left += 1
            } else {
                result.append([newNums[i], newNums[left], newNums[right]])
                
                while right > left && newNums[right] == newNums[right-1] {
                    right -= 1
                }
                while right > left && newNums[left] == newNums[left+1] {
                    left += 1
                }
                // 找到答案时，双指针同时收缩
                right -= 1
                left += 1
            }
        }
    }
    return result
}