文章 217
评论 6
浏览 143919
Array - 16. 3Sum Closest

Array - 16. 3Sum Closest

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
}

标题:Array - 16. 3Sum Closest
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/12/25/1577288333252.html

Nothing just happens, it's all part of a plan.

取消