16. 最接近的三数之和

mid

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

排序 + 对撞指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func abs(x int) int {
   if x < 0 {
      return -x
   }
   return x
}

// 排序+双指针
func threeSumClosest(nums []int, target int) int {
   sort.Ints(nums)
   minDiff := math.MaxInt32
   resultSum := math.MaxInt32
   for index := 1; index < len(nums)-1; index++ {
      start, end := 0, len(nums)-1
      for start < index && end > index {
         curSum := nums[start] + nums[index] + nums[end]
         curDiff := curSum - target

         if abs(curDiff) < minDiff {
            minDiff = abs(curDiff)
            resultSum = curSum
         }

         switch {
         case curDiff == 0:
            return resultSum
         case curDiff < 0:
            start++
         default:
            end--
         }
      }
   }
   return resultSum
}