การหาสามจำนวน (Triplets) ที่ไม่ซ้ำกันและมีผลรวมเป็นศูนย์ใน C#

วิธีง่าย: ลูปซ้อน 3 ชั้น ตรวจสอบผลรวม 3 ตัว วิธีดีกว่า: ใช้ HashSet เก็บค่า ค้นหาใน O(1) สำหรับแต่ละคู่ หาค่าตรงข้ามของผลรวม Time O(n²) Space O(n)

โค้ดตัวอย่างใช้ Two Pointers หลังจัดเรียง เพื่อหา Triplets ที่ไม่ซ้ำกันและผลรวมเป็นศูนย์

Time Complexity: O(N²)

Space Complexity: O(N) สำหรับการจัดเรียงและเก็บผลลัพธ์

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

public class Arrays
{
    public List<List<int>> ThreeSum(int[] nums)
    {
        List<List<int>> res = new List<List<int>>();
        if (nums == null || nums.Length < 3)
        {
            return res;
        }
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 2; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // ข้ามค่าซ้ำ
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0)
                {
                    res.Add(new List<int> { nums[i], 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, 2, -1, -4 };
    var ss = s.ThreeSum(nums);
    foreach (var item in ss)
    {
        Console.WriteLine(string.Join(", ", item));
    }
}

ผลลัพธ์

-1, -1, 2
-1, 0, 1