package main

import (
	"sort"
)

// same as three sum
func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	min := 1<<31 - 1
	res := 0
	for a := 0; a < len(nums)-2; a++ {
		// do NOT skip duplicated numbers!
		// [1 1 1 0], 100 -(skip 1)-> [1 1 0] 100 -> 2, WA
		b, c := a+1, len(nums)-1
		for b < c {
			sum := nums[a] + nums[b] + nums[c]
			if abs(sum-target) < min {
				res = sum
				min = abs(sum - target)
			}
			if sum < target {
				b++
			} else if sum > target {
				c--
			} else {
				return sum
			}
		}
	}
	return res
}

/* func main() {
	a1 := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println(threeSumClosest(a1, 0))

	a2 := []int{-1, 0, -4}
	fmt.Println(threeSumClosest(a2, 0))

	a3 := []int{1, 1, 1, 0}
	fmt.Println(threeSumClosest(a3, 100))
} */