Cách tìm bộ ba số (triplet) duy nhất gần giá trị mục tiêu nhất trong C#

Sử dụng mẫu Two Pointers, tương tự bài toán 3Sum. Duyệt mảng, tại mỗi bước lưu độ chênh lệch giữa tổng bộ ba và target, so sánh với chênh lệch nhỏ nhất để trả về bộ ba gần target nhất.

Độ phức tạp thời gian: Sort O(N log N), tổng thể O(N²).

Độ phức tạp không gian: O(N) cho sắp xếp.

Ví dụ

public class Arrays
{
    public int ThreeSumClosest(int[] num, int target)
    {
        if (num == null || num.Length < 3)
        {
            return -1;
        }
        int[] nums = num.OrderBy(x => x).ToArray();
        int initialClosest = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.Length - 2; i++)
        {
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right)
            {
                int newClosest = nums[i] + nums[left] + nums[right];
                if (Math.Abs(newClosest - target) < Math.Abs(initialClosest - target))
                {
                    initialClosest = newClosest;
                }
                if (newClosest == target)
                {
                    return newClosest;
                }
                else if (newClosest < target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return initialClosest;
    }
}

static void Main(string[] args)
{
    Arrays s = new Arrays();
    int[] nums = { -1, 2, 1, -4 };
    Console.WriteLine(s.ThreeSumClosest(nums, 1)); // Output: 2
}

Kết quả đầu ra

2