2019年08月22日【LeekCode题库problem-16】

GitHub 地址:coffeeTu-code

LeekCode 地址:题库

Language:Golang

/*

@题目

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

@示例:

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

@题目大意

给定一个数组,要求在这个数组中找出 3 个数之和离 target 最近。

@解题思路

这一题的解法是用两个指针夹逼的方法。先对数组进行排序,i 从头开始往后面扫。这里同样需要注意数组中存在多个重复数字的问题。具体处理方法很多,可以用 map 计数去重。这里笔者简单的处理,i 在循环的时候和前一个数进行比较,如果相等,i 继续往后移,直到移到下一个和前一个数字不同的位置。j,k 两个指针开始一前一后夹逼。j 为 i 的下一个数字,k 为数组最后一个数字,由于经过排序,所以 k 的数字最大。j 往后移动,k 往前移动,逐渐夹逼出最接近 target 的值。

*/

func threeSumClosest(nums []int, target int) int {
 sum, res, diff := 0, 0, math.MaxInt32
 sort.Ints(nums)
 for i := 0; i < len(nums)-2; i++ {
 for j, k := i+1, len(nums)-1; j < k; {
 sum = nums[i] + nums[j] + nums[k]
 if sum == target {
 return target
 } else if sum > target {
 k--
 if sum-target < diff {
 res, diff = sum, sum-target
 }
 } else {
 j++
 if target-sum < diff {
 res, diff = sum, target-sum
 }
 }
 }
 }
 return res
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传