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

L千年老妖 · · 1279 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题目：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
  }

有疑问加站长微信联系（非本文作者）