leetcode刷题记录Array篇(16〜3 Sum closest)

题目:Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

翻译:给定n个整数的数组S,在S中找到三个整数,使得和最接近一个给定的数目target。 返回三个整数的总和。 你可以假设每个输入都只有一个解决方案。

思路:这题的思路和15题3sum差不多,只是结果变成最接近某个数,而不是等于0,并且只需要返回最小的结果,斌不需要筛除相同的结果,所以该题在细节上的处理并没有之前那道题多。
1.先排序,给结果一个初始值
2.循环遍历数组,对当前下标索引之后的元素进行首尾遍历,即low,high
3.当nums[i]+nums[low]+nums[high]-target的绝对值小于result-target的绝对值,则把当前的sum赋值给result
4.当sum>target,则需要把sum的值减小,使得sum更接近target,则要把high--,当sum<target,low++

golang代码:

package main
 import (
 "fmt"
 "sort"
 )
 func main() {
 nums := []int{1, 2, 5, 13, -1, 3}
 fmt.Println(threeSumClosest(nums, 5))
 }
 func threeSumClosest(nums []int, target int) int {
 sort.Ints(nums)
 arrLen := len(nums)
 result := nums[0] + nums[1] + nums[arrLen-1]
 var sum int //三个数组相加的值
 if len(nums) < 3 {
 return 0
 }
 for i := 0; i < arrLen; i++ {
 low, high := i+1, arrLen-1
 for low < high {
 sum = nums[i] + nums[low] + nums[high]
 if sum > target {
 high--
 } else {
 low++
 }
 if abs(sum-target) < abs(result-target) {
 result = sum
 }
 }
}
 return result
}
 //求绝对值
 func abs(a int) int {
 if a < 0 {
 return -a
 }
 if a == 0 {
 return 0
 }
 return a
 }

本文来自:简书

感谢作者:L千年老妖

查看原文:leetcode刷题记录Array篇(16〜3 Sum closest)

• 编辑
• 预览