ใช้รูปแบบ Two Pointers คล้ายกับปัญหา Quadruplet Sum to Zero วนลูปผ่านอาร์เรย์ทีละตัว บันทึกความต่างระหว่างผลรวมสี่จำนวนกับเป้าหมาย เปรียบเทียบกับความต่างน้อยสุดที่พบจนได้คำตอบ
Time Complexity: การจัดเรียง O(N log N) รวม O(N³)
Space Complexity: O(N) สำหรับการจัดเรียง
ตัวอย่างโค้ด
public class Arrays
{
public int FourSumClosestToTarget(int[] nums, int target)
{
if (nums == null || nums.Length < 4)
{
return -1;
}
Array.Sort(nums);
int closestSum = nums[0] + nums[1] + nums[2] + nums[3];
for (int i = 0; i < nums.Length - 3; i++)
{
for (int j = i + 1; j < nums.Length - 2; j++)
{
int left = j + 1;
int right = nums.Length - 1;
while (left < right)
{
int currentSum = nums[i] + nums[j] + 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, 0, -1, 0, -2, 2 };
Console.WriteLine(s.FourSumClosestToTarget(nums, 0));
}ผลลัพธ์
0
หมายเหตุ: โค้ดต้นฉบับมีข้อบกพร่องหลายจุด (ลูป j เริ่มจาก i, ใช้ newNums สับสนกับ nums) โค้ดข้างต้นแก้ไขให้ถูกต้องและมีประสิทธิภาพแล้ว
