Swift ～ 三数之和

leetcode.三数之和

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

具体解题实现

• 对数组进行排序
• 转换为双指针问题，left--> <--right

来自网络盗图，数组应该已排序.png

func threeSum(_ nums: [Int]) -> [[Int]] {
    if nums.count < 3 { return [] }
    var nums = nums.sorted()
    let target = 0
    var result : [[Int]] = []
    for a in 0 ..< nums.count - 2 {
        // 转换为双指针（b 、 c）问题
        var b = a + 1
        var c = nums.count - 1
        
        // 剪枝，避免不必要的循环
        if (nums[a] > target) {break}
        if (nums[a] + nums[a + 1] + nums[a + 2] > target) { break }
        if (a > 0 && nums[a] == nums [a - 1]) { continue }
        if (nums[a] + nums[c] + nums[c - 1] < target) { continue }
        
        //  双指针左右逼进
        while (b < c) {
            let sum = nums[a] + nums[b] + nums[c]
            if sum > target {
                c -= 1
                while (b < c && nums[c] == nums [c + 1]) { c -= 1 }
            }
            // 符合条件的三元组输出
            else if sum == target {
                result.append([nums[a], nums[b] , nums[c]])
                b += 1
                c -= 1
                while (b < c && nums[c] == nums [c + 1]) { c -= 1 }
                while (b < c && nums[b] == nums [b - 1]) { b += 1 }
            }
                
            else {
                b += 1
                while (b < c && nums[b] == nums [b - 1]) { b += 1 }
            }
        }
    }
    return result
}