1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (hash.find(complement) != hash.end()) {
                return {hash[complement], i};
            }
            hash[nums[i]] = i;
        }
        // Return an empty vector if no solution is found
        return {};
    }
};

1. Cơ chế hoạt động (Thuật toán "Một lần duyệt")

Ý tưởng cốt lõi là: Khi bạn đứng tại con số hiện tại (nums[i]), thay vì đi tìm số còn lại trong mảng, bạn hãy tự hỏi: "Số mình cần tìm (target - nums[i]) đã xuất hiện trước đó chưa?"

complement = target - nums[i]: Đây là con số còn thiếu để tạo thành tổng target.
hash.find(complement): Kiểm tra xem số còn thiếu này đã được lưu trong Bảng băm chưa.
hash.end(): Đây là một ký hiệu đặc biệt (như trang cuối cùng trống trơn của cuốn sổ), đại diện cho việc "không tìm thấy gì cả".
=> != hash.end() có nghĩa là: "Kết quả tìm kiếm khác với cái trang trống cuối cùng", tức là "ĐÃ TÌM THẤY".
hash[nums[i]] = i: Nếu chưa tìm thấy, ta "ghi nhớ" con số hiện tại và vị trí của nó vào Bảng băm để các số đứng sau có thể tìm thấy nó.

2. Ví dụ minh họa

Giả sử: nums = [2, 7, 11, 15], target = 9

Bước	Số hiện tại (nums[i])	Cần tìm (complement)	Trạng thái Bảng băm	Kết quả
1	2	9 - 2 = 7	Trống. Lưu `{2: 0}`	Tiếp tục
2	7	9 - 7 = 2	Thấy 2 tại index 0!	Trả về {0, 1}

3. Đánh giá độ phức tạp

Độ phức tạp thời gian (O(n)): Chúng ta chỉ duyệt qua mảng đúng một lần. Mỗi thao tác tìm kiếm và thêm vào unordered_map trung bình chỉ mất thời gian hằng số O(1).
Độ phức tạp không gian (O(n)): Trong trường hợp xấu nhất, bạn sẽ phải lưu tất cả n phần tử vào Bảng băm.

4. Tại sao code này lại tốt?

Sử dụng unordered_map: Trong C++, unordered_map dùng bảng băm nên nhanh hơn map (dùng cây đỏ đen, O(log n)) cho mục đích tìm kiếm đơn giản này.
Xử lý thông minh: Việc vừa kiểm tra vừa thêm phần tử vào map giúp tránh trường hợp một số tự cộng với chính nó (trừ khi mảng có hai số giống nhau ở hai vị trí khác nhau).
Cú pháp hiện đại: Sử dụng {hash[complement], i} là cách khởi tạo vector nhanh (Initializer list) từ C++11.

Một lưu ý nhỏ: Trong một số môi trường lập trình thi đấu, unordered_map có thể bị "hack" dẫn đến tốc độ giảm xuống O(n) trong trường hợp xấu nhất. Tuy nhiên, với các bài phỏng vấn và LeetCode, đây vẫn là cách tiếp cận tối ưu nhất.