Array - 16. 3Sum Closest

ppxai

发布于 2020-09-23 17:47:19

3240

发布于 2020-09-23 17:47:19

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).

思路：

给定一个数组，找出三个数的和最接近target，和15题很像，做法类似，都是对于每一位元素，用双指针找出另外两个数，更新出一个最小的结果就可以。

代码：

go：

func threeSumClosest(nums []int, target int) int {

    if nums == nil || len(nums) <= 2 {
        return math.MinInt32
    }
    
    res := nums[0] + nums[1] + nums[len(nums) - 1]
    sort.Ints(nums)
    for i := 0; i < len(nums) - 2; i++ {
        start := i + 1
        end := len(nums) - 1
        for start < end {
            sum := nums[i] + nums[start] + nums[end]
            if sum > target {
                end--
            } else {
                start++
            }
            if abs(sum - target) < abs(res - target) {
                res = sum
            }
        }
    }
    
    return res
    
}

func abs(i int) int {
    if i < 0 {
        return -i
    }
    
    return i
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年12月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

input