Two Sum

Bài toán

Cho một mảng các số nguyên nums và một số nguyên đích target. Hãy trả về chỉ số (indices) của hai số trong mảng sao cho tổng của chúng bằng target. Giả định rằng mỗi đầu vào đều có chính xác một giải pháp, và bạn không được sử dụng cùng một phần tử hai lần.

Ví dụ:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Giải thích: Vì nums[0] + nums[1] == 9, ta trả về [0, 1].

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

Cách 1: Brute Force

Dùng hai vòng lặp lồng nhau. Với mỗi phần tử x, ta tìm xem có phần tử y nào phía sau mà y = target - x không.

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(1)$.

Cách 2: Hash Map (One-pass) - Khuyên dùng "Big Tech"

Ta duyệt qua mảng một lần. Tại mỗi phần tử nums[i], ta cần tìm xem giá trị bù complement = target - nums[i] đã xuất hiện trước đó chưa. Sử dụng một Hash Map để lưu trữ cặp giá trị: chỉ số (val : index) của các phần tử đã duyệt qua.

function twoSum(nums: number[], target: number): number[] {
    // Map lưu trữ: giá trị -> chỉ số (index)
    const prevMap = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const diff = target - num;

        // Kiểm tra xem phần tử bù (diff) đã có trong map chưa
        if (prevMap.has(diff)) {
            return [prevMap.get(diff)!, i];
        }

        // Lưu giá trị hiện tại và chỉ số của nó vào map
        prevMap.set(num, i);
    }

    return [];
}

Quy trình chạy (Dry Run) với nums = [2, 1, 5, 3], target = 4:

1. i=0, num=2. diff=2. Map rỗng. Thêm [2: 0].
2. i=1, num=1. diff=3. Map không có 3. Thêm [1: 1]. Map giờ là {2:0, 1:1}.
3. i=2, num=5. diff=-1. Map không có -1. Thêm [5: 2].
4. i=3, num=3. diff=1. Map CÓ 1 (index 1). Return [1, 3].

• Time Complexity: $O(n)$ - Chỉ duyệt 1 lần, các thao tác Map là $O(1)$.
• Space Complexity: $O(n)$ - Cần lưu trữ tối đa $n$ phần tử trong Map.

Pattern Nhận Diện

Khi gặp bài toán dạng "Tìm cặp giá trị thỏa mãn điều kiện X":

1. Nếu mảng chưa sắp xếp: Nghĩ ngay đến Hash Map. Ta có thể lưu lại những thứ đã thấy để tra cứu ngược lại trong tương lai.
2. Nếu mảng đã sắp xếp: Nghĩ đến Two Pointers (Con trỏ trái/phải), sẽ tối ưu không gian hơn ($O(1)$ space).

Lưu ý cho Frontend Dev

Trong JavaScript/TypeScript:

• Có thể dùng Object {} thay cho Map.
• Tuy nhiên, Map tốt hơn khi:
  • Key là số (Object key luôn bị convert sang string).
  • Cần hiệu năng thêm/xóa cao hơn trong các vòng lặp lớn.