16. 最接近的三数之和(Swift版)

一、题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

二、解题

此题思路和15. 三数之和(Swift版)基本一致，同样是利用移动left和right，但题目是sum离target最近，所以需要判断下当abs(sum - target) <= abs(result! - target)时，sum才算离target最近，将sum赋值给result，遍历排序后的数组，即可找到最接近target的sum。
时间复杂度为O(nlog(n))

三、代码实现

    class Solution {
        func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
            var result: Int? = nil
            if nums.count < 3 {
                return 0
            }
            let arr = nums.sorted()
            
            for i in 0..<arr.count-2 {
                let first = arr[i]
                if i > 0 && arr[i] == arr[i-1] {
                    continue
                }
                var left = i + 1
                var right = arr.count - 1
                while left < right {
                    let sum = first + arr[left] + arr[right]
                    if result == nil || abs(sum - target) <= abs(result! - target) {
                        result = sum
                    }
                    if sum == target {
                        return result!
                    }else if sum < target {
                        left += 1
                    }else{
                        right -= 1
                    }
                }
            }
            return result ?? 0
        }
    }

Demo地址：github