15. 三数之和

本来想着dfs+剪枝的= = 去重也做了啊 结果超时。。
好吧换方法

func threeSum(_ nums: [Int]) -> [[Int]] {

    
        let len = nums.count
        if len < 3 {
            return []
        }
        let sortNums = nums.sorted()
        var ans = [[Int]]()
        var sum = 0
        var tempArray = [Int]()
        dfs(0,0,sortNums,len,&tempArray,&sum,&ans)
        return ans
    
    }
    
    func dfs(_ index:Int,_ begin:Int,_ sortNums:[Int],_ len:Int,_ tempArray:inout [Int],_ sum:inout Int,_ ans:inout [[Int]]  ) {
        
        if index == 3 {
            if sum == 0 {
                ans.append(tempArray)
            }
            return
            
        }
        
        for i in begin..<len{
        
           if i > begin && sortNums[i] == sortNums[i - 1] {
                continue
            }
            
            sum += sortNums[i]
            tempArray.append(sortNums[i])
            dfs(index + 1,i + 1,sortNums,len,&tempArray,&sum,&ans)
            sum -= tempArray.removeLast()
            
        }
        
    }

三指针版本

func threeSum(_ nums: [Int]) -> [[Int]] {

    
        let len = nums.count
        if len < 3 {
            return []
        }
        let sortNums = nums.sorted()
        var ans = [[Int]]()
        let lastIndex = len - 2
        var r = 0 ,c = 0
        for i in 0..<lastIndex{
            
            c = i + 1
            r = len - 1
            let numI = sortNums[i]
            if i > 0 && sortNums[i - 1] == numI {
                continue
            }
            
            while c < r {
                let numC = sortNums[c]
                let numR = sortNums[r]
                let sum = numR + numC + numI
                //说明值偏大了
                if  sum > 0 {
                    r -= 1
                }else if sum < 0{
                    c += 1
                }else {
                    ans.append([numI,numC,numR])
                    //跳过相同的值
                    while c < r && numC == sortNums[c + 1]{
                        c += 1
                    }
                    while c < r && numR == sortNums[r - 1]{
                        r -= 1
                    }
                    c += 1
                    r -= 1
                }
            }
            
        }
  
        return ans
    
    }