การหาสามจำนวน (Triplet) ที่ไม่ซ้ำกันและมีผลรวมใกล้ Target มากที่สุดใน C#

ใช้ Two Pointers คล้าย Triplet Sum to Zero วนลูปทีละตัว บันทึกความต่างระหว่างผลรวมสามจำนวนกับเป้าหมาย เปรียบเทียบกับความต่างน้อยสุดจนได้ triplet ที่ผลรวมใกล้เป้าหมายที่สุด

Time Complexity: จัดเรียง O(N log N) รวม O(N²)

Space Complexity: O(N) สำหรับการจัดเรียง

ตัวอย่างโค้ด

public class Arrays
{
    public int ThreeSumClosest(int[] nums, int target)
    {
        if (nums == null || nums.Length < 3)
        {
            return -1;
        }
        Array.Sort(nums);
        int closestSum = 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 currentSum = nums[i] + nums[left] + nums[right];
                if (Math.Abs(currentSum - target) < Math.Abs(closestSum - target))
                {
                    closestSum = currentSum;
                }
                if (currentSum == target)
                {
                    return currentSum;
                }
                else if (currentSum < target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return closestSum;
    }
}

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

ผลลัพธ์

2