16. 3Sum Closest

Đề bài

Cho mảng số nguyên nums và số nguyên target. Hãy chọn 3 phần tử trong nums sao cho tổng của chúng gần target nhất.

Trả về tổng của 3 số đó. Bạn có thể giả sử mỗi test chỉ có đúng một đáp án.

Ví dụ:

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: Tổng gần nhất là 2 vì (-1 + 2 + 1 = 2).

Tóm tắt đề

Tìm giá trị sum = a + b + c sao cho $|sum - target|$ là nhỏ nhất.

Ý tưởng

Trong file này có 2 cách:

• Cách 1 (khuyến nghị): Sort + 2 con trỏ cho từng i để đạt $O(n^2)$.
  • Sắp xếp nums.
  • Cố định i, rồi dùng j = i+1 và k = n-1 để “kẹp” dần về phía nhau.
  • Mỗi bước cập nhật đáp án tốt nhất nếu $|sum-target|$ nhỏ hơn hiện tại.
  • Nếu sum > target thì giảm k, nếu sum < target thì tăng j.
  • Bỏ qua trường hợp nums[i] bị lặp để tránh tính lại không cần thiết.
• Cách 2: Brute force 3 vòng lặp $O(n^3)$ (dễ hiểu nhưng chậm).

Code

package leetcode

import (
	"math"
	"sort"
)

// Cách 1: O(n^2) - sắp xếp + 2 con trỏ
func threeSumClosest(nums []int, target int) int {
	n, res, diff := len(nums), 0, math.MaxInt32
	if n > 2 {
		sort.Ints(nums)
		for i := 0; i < n-2; i++ {
			if i > 0 && nums[i] == nums[i-1] {
				continue
			}
			for j, k := i+1, n-1; j < k; {
				sum := nums[i] + nums[j] + nums[k]
				if abs(sum-target) < diff {
					res, diff = sum, abs(sum-target)
				}
				if sum == target {
					return res
				} else if sum > target {
					k--
				} else {
					j++
				}
			}
		}
	}
	return res
}

// Cách 2: brute force O(n^3)
func threeSumClosest1(nums []int, target int) int {
	res, difference := 0, math.MaxInt16
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				if abs(nums[i]+nums[j]+nums[k]-target) < difference {
					difference = abs(nums[i] + nums[j] + nums[k] - target)
					res = nums[i] + nums[j] + nums[k]
				}
			}
		}
	}
	return res
}

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

---