LeetCode 16. 3Sum Closest

题目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).  

思路

2sum,3sum这些题目的套路, left and right pointer 来解决, 如果left + right < target, 则left 继续加, 如果> target则right 继续减

swift 题解

func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {  
        if nums.count <= 3 {
            let total = nums.reduce(0, +)
            return total
        }

        let sorted = nums.sorted()

        var current = -1000
        for i in 0...(nums.count - 3) {
            var left = i + 1
            var right = nums.count - 1
            while left < right {
                let sum = sorted[i] + sorted[left] + sorted[right]
                if abs(sum - target) < abs(current - target) {
                    current = sum
                }

                if sum > target {
                    right -= 1
                } else if sum < target {
                    left += 1
                } else {
                    return target
                }
            }
        }

        return current
    }

chenbo

编程爱好者

Singapore