Sử dụng mẫu Two Pointers, tương tự bài toán tổng 4 số bằng 0. Duyệt mảng, tại mỗi bước lưu hiệu giữa tổng bộ bốn và target, so sánh với hiệu nhỏ nhất hiện tại để cuối cùng trả về bộ bốn có tổng gần target nhất.
Độ phức tạp thời gian: Sắp xếp O(N log N). Tổng thể O(N³).
Độ phức tạp không gian: O(N) cho việc sắp xếp.
Ví dụ
public class Arrays
{
public int FourSumClosestToTarget(int[] nums, int target)
{
if (nums == null || nums.Length < 4)
{
return -1;
}
int[] newNums = nums.OrderBy(x => x).ToArray();
int initialSum = newNums[0] + newNums[1] + newNums[2] + newNums[3];
for (int i = 0; i < newNums.Length - 3; i++)
{
for (int j = i + 1; j < newNums.Length - 2; j++)
{
int left = j + 1;
int right = newNums.Length - 1;
while (left < right)
{
int nearestSum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
if (Math.Abs(nearestSum - target) < Math.Abs(initialSum - target))
{
initialSum = nearestSum;
}
if (nearestSum == target)
{
return nearestSum;
}
else if (nearestSum < target)
{
left++;
}
else
{
right--;
}
}
}
}
return initialSum;
}
}
static void Main(string[] args)
{
Arrays s = new Arrays();
int[] nums = { 1, 0, -1, 0, -2, 2 };
var ss = s.FourSumClosestToTarget(nums, 0);
Console.WriteLine(ss); // Output: 0
}
Kết quả đầu ra
0
Lưu ý: Code gốc có lỗi logic so sánh nearestSum < initialSum thay vì so sánh độ chênh lệch với target. Phiên bản trên đã sửa dùng Math.Abs. Cũng sửa điều kiện vòng lặp j = i → j = i + 1 và giới hạn i, j hợp lý.