Cách tìm tất cả bộ bốn số (quadruplets) duy nhất có tổng bằng 0 trong C#

Cách đơn giản: 4 vòng lặp lồng nhau kiểm tra tổng 4 phần tử có bằng 0 không (O(n⁴)). Cách tối ưu: dùng Two Pointers sau khi sắp xếp, giảm xuống O(n³). Lưu trữ kết quả trong List<List<int>>, bỏ qua các phần tử trùng lặp để đảm bảo bộ bốn duy nhất.

Độ phức tạp thời gian: O(n³) sau khi sort O(n log n)

Độ phức tạp không gian: O(n) cho kết quả và sắp xếp

Ví dụ

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; // bỏ qua trùng lặp i
            for (int j = i + 1; j < nums.Length - 2; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // bỏ qua trùng lặp 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) + "]");
    }
    // Output: [-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]
}

Kết quả đầu ra

[-2,-1,1,2]
[-2,0,0,2]
[-1,0,0,1]

Lưu ý: Code gốc dùng OrderBy tạo mảng mới nhưng logic bỏ qua trùng lặp tham chiếu mảng gốc nums gây lỗi. Phiên bản trên dùng Array.Sort trực tiếp trên nums và logic bỏ trùng lặp chuẩn chuẩn.