package main

import (
	"math"
	"sort"
)

// 16. 最接近的三数之和
// 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
// 返回这三个数的和。
// 假定每组输入只存在恰好一个解。
func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	ans := 0              // 题目设定是有解的，所以初始值不重要
	diff := math.MaxInt32 // int32，而不是int
	for i := 0; i < len(nums)-2; i++ {
		//for i != 0 && nums[i] == nums[i-1] { // 只有一个解，其实不需要去重
		//	i++
		//}
		start := i + 1
		end := len(nums) - 1
		for start < end {
			sum := nums[i] + nums[start] + nums[end]
			if abs(sum-target) < diff {
				diff = abs(sum - target)
				ans = sum
			}
			if sum == target {
				return ans
			} else if sum > target { // 题目设定只有一个解，所以就不需要像15题那样去重了
				end--
			} else {
				start++
			}
		}
	}
	return ans
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

// 三数之和变种题，判断三数之和和target之差，即可