Two Sum: từ brute force O(n²) xuống một lượt duyệt hash-map

Two Sum là bài hầu hết mọi người giải đầu tiên, và nó âm thầm là một lời chào hàng cho hash map. Bản brute force chỉ là hai dòng vòng lặp lồng nhau, và nó chạy được. Phần thú vị là cái ý tưởng duy nhất biến hai vòng lặp đó thành một lượt duyệt — vì chính ý tưởng đó xuất hiện trong cả tá bài khó hơn.

Đề bài

Cho mảng nums và một target, trả về chỉ số của hai số có tổng bằng target. Đề bảo đảm đúng một nghiệm, và bạn không được dùng lại một phần tử. Ràng buộc định hình mọi thứ: mảng có thể tới 10⁴ số, và phần follow-up hỏi thẳng một cách tốt hơn O(n²).

Cái follow-up đó chính là toàn bộ bài tập. Brute force được phép tồn tại; mục tiêu là vượt qua nó.

Brute force, và vì sao tôi vẫn viết nó trước

Kiểm tra mọi cặp. Cặp nào có tổng bằng target thì trả về chỉ số.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

O(n²) thời gian, O(1) bộ nhớ. Trên mảng 10⁴ phần tử, đó là cả trăm triệu phép so sánh ở trường hợp xấu nhất — chậm, nhưng chưa thảm hoạ, và đó đúng là cái bẫy: nó qua được các test nhỏ và ru ngủ bạn. Trong phỏng vấn tôi vẫn viết nó trước, nói thành lời, vì nó phát biểu bài toán chính xác và cho tôi một thứ đúng để tối ưu từ đó. Nhảy thẳng tới lời giải khôn ngoan là bỏ qua đúng phần lập luận mà người phỏng vấn muốn nghe.

Mẹo duy nhất: lật ngược câu hỏi

Vòng lặp lồng nhau hỏi, với mỗi i, "có j phía sau nào hoàn thành cặp không?" Cách đó quét lại mảng n lần. Lật câu hỏi: khi duyệt mảng một lượt, với số hiện tại x, thật ra tôi đang hỏi "mình đã thấy target - x chưa?" Giá trị đó có tên — complement — và "đã thấy chưa" đúng là thứ hash map trả lời trong O(1).

Vậy tôi giữ một map giá trị → chỉ số cho mọi thứ đã đi qua. Mỗi bước tôi tra complement trước khi chèn số hiện tại. Nếu nó có sẵn, xong.

Một lượt duyệt, một map

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}                       # value -> index
        for i, x in enumerate(nums):
            if target - x in seen:
                return [seen[target - x], i]
            seen[x] = i

Cùng dạng đó trong C#:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var seen = new Dictionary<int, int>();   // value -> index
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (seen.TryGetValue(complement, out int j)) {
                return new[] { j, i };
            }
            seen[nums[i]] = i;
        }
        return Array.Empty<int>();
    }
}

O(n) thời gian, O(n) bộ nhớ. Thứ tự quan trọng: tra complement trước khi chèn giá trị hiện tại, nếu không một phần tử có thể tự khớp với chính nó khi target đúng bằng 2 * x. Đây là bản tôi ship.

Sao không sort rồi dùng two pointers?

Sort cộng two pointers cũng cho O(n log n) và O(1) bộ nhớ thêm, và với biến thể mảng đã sắp xếp (Two Sum II) thì đó là lựa chọn đúng. Ở đây thì không, vì một lý do thẳng thừng: sort phá huỷ chỉ số gốc, mà đề lại hỏi chỉ số chứ không phải giá trị. Bạn sẽ phải mang theo vị trí gốc của từng số qua bước sort rồi trả lại — nhiều code hơn, nhiều chỗ sai hơn, và chậm hơn O(n) của hash map. Khi đáp án là "vị trí trong input", một map giá trị → chỉ số gần như luôn thắng.

Cái dạng bài đáng giữ

Two Sum không đáng học thuộc. Nước đi tái dùng được là: thay vì đi tìm một cặp, hãy lưu những gì đã thấy và hỏi xem cái hoàn thành phần tử hiện tại có sẵn chưa. Một map seen biến "tìm phần tử khớp" từ một lượt quét trong O(n) thành một tra cứu O(1).

Bạn gặp lại nước đi này liên tục:

• Contains Duplicate (217) — trường hợp suy biến: complement chính là số đó.
• Two Sum II — mảng đã sắp xếp (167) — đã sort, nên bỏ map mà dùng two pointers.
• 3Sum (15) — cố định một số, phần còn lại là Two Sum.
• Subarray Sum Equals K (560) — cùng mẹo trên prefix sum: "đã thấy prefix - k chưa?"

Nếu lấy một thói quen từ bài này, hãy để nó là phản xạ với tay tới map seen ngay khi bạn bắt gặp mình đang viết vòng lặp thứ hai chỉ để tìm một giá trị khớp. Two Sum là chỗ rẻ nhất để học rằng đúng cấu trúc dữ liệu sẽ xoá sạch cả một vòng lặp.