รูปแบบ Two Pointers และคล้ายกับ Triplet Sum ถึง Zero เราสามารถทำตามแนวทางเดียวกันนี้เพื่อวนซ้ำผ่านอาร์เรย์ โดยนำตัวเลขมาทีละตัว ในทุกขั้นตอน เราจะบันทึกส่วนต่างระหว่างแฝดสามกับหมายเลขเป้าหมาย และในแต่ละขั้นตอน เราจะเปรียบเทียบกับความแตกต่างของเป้าหมายขั้นต่ำจนถึงตอนนี้ เพื่อที่ในท้ายที่สุด เราสามารถส่งคืนแฝดสามด้วยผลรวมที่ใกล้เคียงที่สุด
ความซับซ้อนของเวลา
การเรียงลำดับอาร์เรย์จะใช้ O(N* logN) โดยรวม threeSumClosest() จะใช้ O(N * logN + N^2) ซึ่งเทียบเท่ากับ O(N^2) แบบไม่แสดงอาการ
ความซับซ้อนของอวกาศ
ความซับซ้อนของช่องว่างของอัลกอริธึมข้างต้นจะเป็น O(N) ซึ่งจำเป็นสำหรับการเรียงลำดับ
ตัวอย่าง
public class Arrays{
public int ThreeSumClosest(int[] num, int target){
if (num == null || num.Length == 0){
return -1;
}
int[] nums = num.OrderBy(x => x).ToArray();
int initialclosest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Count(); 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));
} ผลลัพธ์
2
