วิธีง่ายคือสร้างลูปซ้อน 4 ชั้น ตรวจสอบผลรวม 4 ตัวว่เป็นศูนย์หรือไม่ Time Complexity O(n⁴) Space O(1) วิธีที่ดีกว่าใช้ HashSet เก็บค่า ค้นหาใน O(1) สำหรับแต่ละคู่ หาค่าตรงข้ามของผลรวมในเซต Time O(n³) Space O(n)
โค้ดตัวอย่างใช้วิธี Two Pointers หลังจัดเรียงอาร์เรย์ เพื่อหา quadruplets ที่ไม่ซ้ำกัน (Unique) และผลรวมเป็นศูนย์
Time Complexity: O(N³)
Space Complexity: O(N) สำหรับการจัดเรียงและเก็บผลลัพธ์
ตัวอย่างโค้ด
public class Arrays
{
public List<List<int>> FourSum(int[] nums)
{
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length < 4)
{
return res;
}
Array.Sort(nums);
for (int i = 0; i < nums.Length - 3; i++)
{
if (i > 0 && nums[i] == nums[i - 1]) continue; // ข้ามค่าซ้ำ i
for (int j = i + 1; j < nums.Length - 2; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // ข้ามค่าซ้ำ j
int left = j + 1;
int right = nums.Length - 1;
while (left < right)
{
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == 0)
{
res.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
int leftVal = nums[left];
int rightVal = nums[right];
while (left < right && nums[left] == leftVal) left++;
while (left < right && nums[right] == rightVal) right--;
}
else if (sum < 0)
{
left++;
}
else
{
right--;
}
}
}
}
return res;
}
}
static void Main(string[] args)
{
Arrays s = new Arrays();
int[] nums = { 1, 0, -1, 0, -2, 2 };
var ss = s.FourSum(nums);
foreach (var item in ss)
{
Console.WriteLine(string.Join(", ", item));
}
}ผลลัพธ์
-2, -1, 1, 2 -2, 0, 0, 2 -1, 0, 0, 1
