3Sum: two pointers bên trong một vòng lặp đã sắp xếp

Bài viết trước về Two Sum II kết thúc với một nhận xét đáng nhớ: sau khi mảng đã được sắp xếp, một pointer trái và một pointer phải có thể tìm bất kỳ cặp mục tiêu nào trong thời gian tuyến tính. 3Sum chính là điều xảy ra khi bạn bọc kỹ thuật đó bên trong một vòng lặp nữa. Cố định phần tử đầu tiên, để Two Sum II xử lý hai phần tử còn lại. Đó là toàn bộ thuật toán — ngoại trừ phần bỏ qua trùng lặp, nơi mà mọi solution trông có vẻ sạch thường lặng lẽ gãy.

Bài toán và constraints cho bạn biết điều gì

Cho một mảng số nguyên, trả về tất cả các bộ ba duy nhất [a, b, c] sao cho a + b + c == 0. Không có bộ ba trùng lặp trong output, và các chỉ số phải khác nhau.

Constraint 3 <= n <= 3000 thực ra đã làm hầu hết công việc cho bạn. 3000³ là khoảng 27 tỷ operations — không khả thi. 3000² là 9 triệu, hoàn toàn ổn. Vậy constraint không chỉ là một giới hạn; nó đang nói với bạn rằng đáp án phải là O(n²). Điều này ngay lập tức loại bỏ approach ba vòng lặp lồng nhau và chỉ hướng bạn đến thứ gì đó giảm inner search từ O(n²) xuống O(n).

Dải giá trị -10⁵ <= nums[i] <= 10⁵ vừa đủ trong một số nguyên 32-bit. Tổng của hai số nằm trong 64-bit int, nhưng ngay cả tổng của ba số cũng không overflow int trong hầu hết các ngôn ngữ. Không cần guard overflow ở đây.

Approach 1: brute force O(n³)

Điểm khởi đầu hiển nhiên: ba vòng lặp lồng nhau qua tất cả các bộ ba index (i, j, k) với i < j < k. Nếu tổng bằng 0, sort bộ ba và chèn vào set để xử lý deduplication.

class Solution:
    def threeSum(self, nums):
        result_set = set()
        n = len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                        result_set.add(triplet)
        return [list(t) for t in result_set]

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var seen = new HashSet<string>();
        var result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 2; i++)
            for (int j = i + 1; j < n - 1; j++)
                for (int k = j + 1; k < n; k++)
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        var t = new[] { nums[i], nums[j], nums[k] };
                        Array.Sort(t);
                        string key = string.Join(",", t);
                        if (seen.Add(key))
                            result.Add(t.ToList());
                    }
        return result;
    }
}

Time: O(n³). Space: O(k) cho output cộng thêm overhead của set. Với n = 3000, đó là khoảng 27 tỷ so sánh — TLE trên mọi ngôn ngữ. Việc dedup bằng set cũng giống như che giấu một lỗi thiết kế hơn là giải quyết nó. Mỗi bộ ba được sort bên trong vòng lặp, thêm hằng số O(1) nhưng báo hiệu cấu trúc không đúng.

Approach 2: hash set reduction O(n²)

Cố định phần tử ngoài ở index i, sau đó biến bài toán tìm hai phần tử còn lại thành lookup Two Sum. Duyệt qua nums[j] với j > i, duy trì một set các giá trị đã thấy, và kiểm tra xem -(nums[i] + nums[j]) đã tồn tại trong set chưa.

class Solution:
    def threeSum(self, nums):
        result_set = set()
        n = len(nums)
        for i in range(n - 1):
            seen = set()
            for j in range(i + 1, n):
                complement = -(nums[i] + nums[j])
                if complement in seen:
                    triplet = tuple(sorted([nums[i], nums[j], complement]))
                    result_set.add(triplet)
                seen.add(nums[j])
        return [list(t) for t in result_set]

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var resultSet = new HashSet<string>();
        var result = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 1; i++) {
            var seen = new HashSet<int>();
            for (int j = i + 1; j < n; j++) {
                int complement = -(nums[i] + nums[j]);
                if (seen.Contains(complement)) {
                    var t = new[] { nums[i], nums[j], complement };
                    Array.Sort(t);
                    string key = string.Join(",", t);
                    if (resultSet.Add(key))
                        result.Add(t.ToList());
                }
                seen.Add(nums[j]);
            }
        }
        return result;
    }
}

Time: O(n²). Space: O(n) cho inner hash set cộng thêm result set.

Approach này đạt được time complexity đúng. Deduplication vẫn phức tạp — bạn phải sort từng candidate trước khi hash, và cần thêm một outer set để dedup qua các iteration ngoài. Nó hoạt động, nhưng đang trả O(n) extra memory và rất nhiều bookkeeping để giải quyết bài toán mà việc sorting xử lý miễn phí. Tôi sẽ không dùng cái này; approach two-pointer đơn giản hơn ở mọi khía cạnh quan trọng.

Approach 3: sort + two pointers O(n²)

Sort mảng một lần. Duyệt với index i từ 0 đến n - 3, coi nums[i] là phần tử đầu tiên cố định. Bên trong, chạy đúng Two Sum II trên subarray nums[i+1 .. n-1]: đặt left = i + 1 và right = n - 1, rồi hội tụ về giữa.

Sorting làm ba việc cùng lúc: làm cho việc di chuyển two-pointer đơn điệu, gom tất cả các giá trị trùng lặp vào các vị trí liền kề (nên việc bỏ qua chúng chỉ cần một vòng while), và cho phép thoát sớm khi nums[i] > 0.

Trace tay: nums = [-1, 0, 1, 2, -1, -4]

Sau sort: [-4, -1, -1, 0, 1, 2]

class Solution:
    def threeSum(self, nums):
        nums.sort()
        result = []
        n = len(nums)
 
        for i in range(n - 2):
            # Thoát sớm: phần tử nhỏ nhất còn lại dương, không có triplet nào
            if nums[i] > 0:
                break
 
            # Bỏ qua giá trị trùng lặp cho phần tử cố định
            if i > 0 and nums[i] == nums[i - 1]:
                continue
 
            left, right = i + 1, n - 1
 
            while left < right:
                total = nums[i] + nums[left] + nums[right]
 
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
 
                    # Bỏ qua trùng lặp từ phía trái
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Bỏ qua trùng lặp từ phía phải
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
 
                    left += 1
                    right -= 1
 
                elif total < 0:
                    left += 1
                else:
                    right -= 1
 
        return result

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);
        var result = new List<IList<int>>();
        int n = nums.Length;
 
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
 
            int left = i + 1, right = n - 1;
 
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
 
                if (total == 0) {
                    result.Add(new List<int> { nums[i], nums[left], nums[right] });
 
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
 
                    left++;
                    right--;
                } else if (total < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
 
        return result;
    }
}

Time: O(n log n) cho sort, O(n²) cho nested scan — bị chi phối bởi O(n²). Space: O(1) nếu bỏ qua output array và stack nội bộ của sort.

Logic bỏ qua trùng lặp, phân tích kỹ

Đây là phần làm hỏng hầu hết các lần thử đầu tiên. Có ba chỗ mà trùng lặp có thể gây ra lỗi, và mỗi chỗ lại thất bại theo cách khác nhau.

Vòng lặp ngoài (i): Sau khi xử lý nums[i], bạn không muốn lặp lại toàn bộ inner scan cho cùng giá trị đó. Kiểm tra if i > 0 and nums[i] == nums[i - 1]: continue xử lý điều này. Guard i > 0 không thể bỏ qua — thiếu nó sẽ skip cả i = 0 khi nums[0] == nums[1], làm mất các triplet hợp lệ.

Các pointer bên trong sau khi tìm thấy kết quả: Khi tìm được một bộ ba, advance cả hai pointer qua mọi run của giá trị giống nhau trước khi tiếp tục. Hai vòng while bên trong nhánh total == 0 làm điều này. Chúng dừng lại trước khi giao nhau (guard left < right) vì nếu tất cả phần tử còn lại giống nhau, các pointer nên kết thúc ở kề nhau, không phải lật ngược — lật ngược sẽ khiến left >= right kết thúc vòng while ngoài, điều đúng nhưng cần guard để không truy cập index ngoài biên.

Điều bạn không cần lo lắng: Các nhánh total < 0 và total > 0 di chuyển một pointer vô điều kiện. Nếu giá trị tiếp theo tình cờ giống nhau, bạn sẽ tìm thấy cùng tổng và di chuyển lại, hoặc tổng thay đổi — không có bộ ba trùng lặp nào được ghi vì bạn chỉ append bên trong total == 0.

Một trường hợp cụ thể gây lỗi: nums = [-2, 0, 0, 2, 2]. Không có inner duplicate-skip:

• i=0, nums[i]=-2, tìm left=1 (0), right=4 (2) -> sum=0, ghi [-2, 0, 2]
• Không skip: left=2 (0), right=3 (2) -> sum=0, ghi [-2, 0, 2] lần nữa

Output mong đợi: [[-2, 0, 2]]. Không đúng khi thiếu skip: [[-2, 0, 2], [-2, 0, 2]].

Các edge case thực sự quan trọng

Tất cả là số 0 [0, 0, 0]: Sau sort, i=0, nums[i]=0, left=1, right=2. Tổng 0+0+0=0, ghi [0,0,0]. Cả hai vòng skip không advance (không có giá trị giống nhau liền kề qua biên), và left++/right-- khiến left >= right. Vòng ngoài tiếp tục nhưng nums[1]=0 bị skip bởi check i > 0 and nums[i] == nums[i-1]. Kết quả: [[0,0,0]]. Đúng.

Tất cả là số dương [1, 2, 3, 4]: Sau sort, nums[0]=1 > 0, nên break kích hoạt ngay lập tức. Kết quả: []. Đúng, và runtime O(1) trong thực tế cho dạng input này.

Tất cả cùng giá trị, khác 0 [1, 1, 1]: Sau sort, i=0, nums[i]=1 > 0, break ngay. Kết quả: []. Đúng.

Trùng lặp nặng [-1, -1, -1, 0, 1, 1, 1]: Vòng skip ngoài kích hoạt với i=1 và i=2 (cả hai bằng nums[0]=-1). Chỉ i=0 chạy inner scan. Bên trong, inner skip kích hoạt nhiều lần để gom các run của 1. Bộ ba duy nhất [-1, 0, 1] được ghi đúng một lần.

Input nhỏ nhất [0, 0, 0]: Đã xử lý ở trên — input hợp lệ nhỏ nhất theo constraint (n >= 3) có đúng một bộ ba có thể và code tìm ra nó.

So sánh các approach

Approach hash set không sai — đó là phần mở rộng tự nhiên của ý tưởng hash map Two Sum 1D. Nhưng O(n) space thêm không mang lại lợi ích gì ở đây; sorting là O(n log n) và loại bỏ nhu cầu lưu trữ phụ nào ngoài output. Tôi sẽ dùng approach sort trong mọi ngữ cảnh: phỏng vấn, production, bảng trắng.

Vị trí bài này trong series two-pointers

Two Sum II (LeetCode 167) đã thiết lập nước đi cốt lõi: sort một bài tìm cặp cố định xuống còn thời gian tuyến tính với two pointers. 3Sum bọc cái đó trong một vòng lặp ngoài, thêm một constraint — duplicate-skip — mà Two Sum II không cần vì bài toán đó đảm bảo phần tử duy nhất. Mọi thứ ở đây chính xác là Two Sum II + một vòng lặp + ba điều kiện skip. Nếu Two Sum II cảm thấy tự nhiên, 3Sum nên cảm thấy như một nâng cấp trực tiếp, không phải một bài toán mới.

Mental model tổng quát hóa: k-Sum giảm về (k-1)-Sum bằng cách cố định một phần tử. Cố định hai phần tử với hai vòng lặp lồng nhau và bạn có 4Sum với O(n³). Cố định ba phần tử với ba vòng lặp và bạn có 5Sum với O(n⁴). Mỗi cấp thêm một vị trí duplicate-skip. Pattern giữ nguyên cho đến tận cùng; trong thực tế không ai làm quá 4Sum.

Bốn bài liên quan đáng làm theo thứ tự

3Sum Closest (LeetCode 16) — thay check total == 0 bằng việc theo dõi min(abs(total - target)). Logic di chuyển two-pointer hoàn toàn giống nhau, chỉ phần bookkeeping thay đổi. Duplicate-skipping trở thành tùy chọn vì bạn đang minimize khoảng cách thay vì thu thập kết quả chính xác. Nên làm ngay sau bài này.

3Sum Smaller (LeetCode 259) — đếm các bộ ba mà tổng nhỏ hơn target cho trước. Cùng outer loop và setup two-pointer, nhưng khi sum < target bạn đếm right - left bộ ba cùng lúc (tất cả giá trị giữa left và right đều ghép với left hiện tại cho tổng nhỏ hơn). Trick đếm là phần không hiển nhiên.

4Sum (LeetCode 18) — phần mở rộng trực tiếp. Hai vòng lặp ngoài, two pointers bên trong. Duplicate-skip ở bốn chỗ thay vì ba. Phần thú vị là O(n³) là tốt nhất có thể đạt được cho 4 phần tử, và cấu trúc code làm điều đó rõ ràng.

Container With Most Water (LeetCode 11) — một cách sử dụng khác của two pointers trên cấu trúc gần-như-sắp-xếp. Bài này không sort và không dedup; trực giác two-pointer là greedy (luôn di chuyển tường ngắn hơn) thay vì hội tụ theo target. Tốt để kiểm tra xem bạn có thực sự hiểu tại sao two pointers hoạt động trên 3Sum so với tại sao chúng hoạt động ở đây — invariant khác nhau.