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

L千年老妖 · · 803 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目: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)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

803 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传