16. 3Sum Closest

Description

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

Tags: Array, Two Pointers

题意

题意是让你从数组中找出最接近 target 的三个数的和

题解

思路1

该题和 3Sum 的思路基本一样,先对数组进行排序,然后遍历这个排序数组,用两个指针分别指向当前元素的下一个和数组尾部,判断三者的和与 target 的差值来移动两个指针,并更新其结果,当然,如果三者的和直接与 target 值相同,那么返回 target 结果即可。

func threeSumClosest(nums []int, target int) int {
    ans := nums[0] + nums[1] + nums[len(nums)-1]
    sort.Ints(nums)
    for i := 0; i < len(nums)-2; i++ {
        start, end := i+1, len(nums)-1
        for start < end {
            sum := nums[i] + nums[start] + nums[end]
            if sum > target {
                end--
            } else {
                start++
            }

            if Abs(sum-target) < Abs(ans-target) {
                ans = sum
            }

        }
    }
    return ans
}

func Abs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}

思路2

思路2 ```go

```

结语

如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:awesome-golang-leetcode

results matching ""

    No results matching ""