3Sum

Bài toán

Cho một mảng số nguyên nums. Trả về tất cả các bộ ba [nums[i], nums[j], nums[k]] sao cho:

• i != j, i != k, j != k
• nums[i] + nums[j] + nums[k] == 0
• Bộ kết quả không được chứa các bộ ba trùng lặp (ví dụ [-1, 0, 1] và [0, 1, -1] coi là trùng).

Ví dụ:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Phân Tích & Tiếp Cận

Cách tiếp cận: Fix một số, tìm 2 số còn lại

Để tìm a + b + c = 0, ta có thể chuyển thành: b + c = -a. Đây chính là bài toán Two Sum! Ta sẽ duyệt qua từng số a trong mảng, và với mỗi a, ta dùng Two Sum II để tìm cặp (b, c) trong phần còn lại của mảng.

Bước chuẩn bị: Sắp xếp (Sorting)

Để tránh trùng lặp dễ dàng và dùng được Two Pointers, ta buộc phải Sắp xếp mảng trước ($O(n \log n)$).

Thuật toán

1. Sort nums.
2. Duyệt i từ 0 đến n-2:
   • Nếu i > 0 và nums[i] == nums[i-1]: Bỏ qua để tránh trùng lặp bộ ba (cùng số đầu tiên).
   • Đặt left = i + 1, right = n - 1.
   • Chạy Two Pointers tìm nums[left] + nums[right] == -nums[i].
     • Nếu tìm thấy: Thêm vào kết quả.
     • Quan trọng: Sau khi tìm thấy, phải dịch chuyển left lên để bỏ qua các số giống nhau (Tránh trùng lặp bộ số thứ 2). Ví dụ [-2, 0, 0, 2, 2]. Sau khi lấy [-2, 0, 2], left đang ở số 0 đầu tiên, phải nhảy qua số 0 thứ hai.

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const res: number[][] = [];

    for (let i = 0; i < nums.length - 2; i++) {
        // Bỏ qua giá trị trùng lặp cho vị trí số 1
        if (i > 0 && nums[i] === nums[i-1]) continue;

        let l = i + 1;
        let r = nums.length - 1;

        while (l < r) {
            const sum = nums[i] + nums[l] + nums[r];

            if (sum > 0) {
                r--;
            } else if (sum < 0) {
                l++;
            } else {
                res.push([nums[i], nums[l], nums[r]]);
                
                // Cập nhật con trỏ và bỏ qua trùng lặp cho vị trí số 2
                l++;
                while (l < r && nums[l] === nums[l-1]) {
                    l++;
                }
                // Không cần xử lý r trùng lặp vì logic sum > 0 phía trên 
                // sẽ tự động lo liệu ở vòng lặp sau, hoặc l tăng thì r buộc phải giảm
            }
        }
    }
    return res;
}

• Time Complexity: $O(n^2)$ - Sắp xếp mất $O(n \log n)$. Vòng lặp i mất $O(n)$, lồng bên trong là Two Pointers $O(n)$ => Tổng $O(n^2)$.
• Space Complexity: $O(n)$ (hoặc $O(\log n)$ tùy thuật toán sort) - chủ yếu là không gian cho việc sort.

Pattern Nhận Diện

Bài toán 3Sum là nền tảng cho k-Sum.

• 2Sum -> Hash Map hoặc Two Pointers.
• 3Sum -> Sort + Loop + Two Pointers.
• k-Sum -> Recursion giảm bậc về 2Sum.

Điểm khó nhất của bài này thực ra là xử lý trùng lặp. Mọi logic nums[i] == nums[i-1] và while (nums[l] == nums[l-1]) đều nhằm mục đích này.