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

Cách đơn giản: 3 vòng lặp lồng nhau O(n³). Cách tối ưu: Sort mảng + Two Pointers O(n²). Duyệt từng phần tử làm cố định, dùng 2 con trỏ left/right tìm cặp còn lại. Bỏ qua phần tử trùng lặp để đảm bảo triplet 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í dụ

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) + "]");
    }
    // Output: [-1,-1,2], [-1,0,1]
}

Kết quả đầu ra

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

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