16. 最接近的三数之和

先dfs,好吧。超时= =。。

func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
      
        var tempArray:[Int] = []
        var ans = 0
        var sum = 0
        var minDecount = Int.max
        let sortNums = nums.sorted()
        dfs(0,sortNums,target,sortNums.count,0,&minDecount,&tempArray,&ans,&sum)
                 
        return ans
    
    
    }
    
    
    func dfs(_ index:Int, _ sortNums:[Int],_ target:Int,_ len:Int,_ begin:Int,_ minDecount:inout Int,_ tempArray: inout [Int],_ ans: inout Int,_ sum:inout Int){
    
        
        if index == 3 {
            var tempDecount = 0
            if sum > target {
                tempDecount = sum - target
            }
            else {
                tempDecount = target - sum
            }

            if tempDecount < minDecount {
                minDecount = tempDecount
                ans = sum
            }

            return
        }
        //每一层可以选择的
        for i in begin..<len {
            let num = sortNums[i]
            sum += num
            tempArray.append(num)
            dfs(index + 1,sortNums.sorted(),target,len,i + 1,&minDecount,&tempArray,&ans,&sum)
            sum -= tempArray.removeLast()
        }

    }

开始三指针= =。。

func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
      
        let sortNums = nums.sorted()
        let len = sortNums.count
        var ans = 0
        var sum = 0
        var decount = Int.max
        var c = 1,r = len - 1
        for i in 0..<len - 2 {
            let num1 = sortNums[i]
            if i > 0 && num1 == sortNums[i - 1] {
                continue
            }
            c = i + 1
            r = len - 1
            while c < r {
                let num2 = sortNums[c]
                let num3 = sortNums[r]
                sum = num1 + num2 + num3
                if sum == target {
                    return sum
                }
                
                var tempDecount = 0
                if sum > target {
                    
                    tempDecount = sum - target
                    r -= 1
                   while c < r && sortNums[r] == sortNums [r - 1] {
                    r -= 1
                   }
                                        
                }else {
                    tempDecount = target - sum
                    c += 1
                    while c < r && sortNums[c] == sortNums [c + 1] {
                        c += 1
                    }
                    
                }
                //说明差值比较小
                if tempDecount < decount {
                    decount = tempDecount
                    ans = sum
                }
               
                
            }
  
            
        }

        
        return ans
    
    
    }