9、3Sum

Problem Description

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)

Analyze

• A.count < 3, 返回空数组
• 先排序，然后做 n − 2 次循环，在最内层循环左右夹逼
• 去重（当前元素与前一个元素相等时不做搜索）

Code

class Solution {
    func threeSum(nums: [Int]) -> [[Int]] {
      
        return generalThreeSum(nums, target: 0)
    }
    
    func generalThreeSum(nums: [Int], target: Int) -> [[Int]] {
        var results = [[Int]]()
        let count = nums.count
        
        if count < 3 { return results }
        
        //  排序
        let nums = nums.sort()
        
        for i in 0..<count-2 {
       
            if i>0 && nums[i] == nums[i-1] { continue } //去重
            
            var begin = i + 1, end = count-1
            while begin < end {
                let curSum = nums[begin] + nums[end]
                let curTaget = target - nums[i]
                
                if curSum == curTaget {
                    let result = [nums[i], nums[begin], nums[end]]
                    results.append(result)
                    
                    begin += 1
                    end -= 1
                    //去重
                    while nums[begin] == nums[begin-1] && begin < end { begin += 1 }
                    while nums[end] == nums[end+1] && begin < end { end -= 1 }
                }
                else if curSum < curTaget {
                    begin += 1
                }
                else {
                    end -= 1
                }
            }
        }
        return results
    }
}