Two Sum II

Bài toán

Cho một mảng số nguyên numbers đã được sắp xếp tăng dần. Tìm hai số sao cho tổng của chúng bằng target. Trả về chỉ số (1-based index) của hai số đó. Bạn không được dùng thêm bộ nhớ quá nhiều (chỉ được dùng $O(1)$ space).

Ví dụ:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2] (Vì 2 + 7 = 9)

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

Tại sao không dùng Hash Map (như Two Sum I)?

Hash Map tốn $O(n)$ bộ nhớ (Space). Đề bài yêu cầu $O(1)$. Hơn nữa, thông tin "mảng đã sắp xếp" chưa được tận dụng nếu dùng Hash Map.

Cách giải: Two Pointers

Vì mảng đã sắp xếp:

• Số nhỏ nhất ở bên trái (left).
• Số lớn nhất ở bên phải (right).

Ta tính sum = numbers[left] + numbers[right]:

1. Nếu sum == target: Bingo! Trả về kết quả.
2. Nếu sum > target: Tổng đang quá lớn. Để giảm tổng, ta cần chọn một số nhỏ hơn. Số bên phải đang là lớn nhất, nên ta phải giảm nó đi -> right--.
3. Nếu sum < target: Tổng đang quá bé. Ta cần tăng tổng lên bằng cách chọn số lớn hơn -> left++.

function twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            // Đề bài yêu cầu 1-based index
            return [left + 1, right + 1];
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return [];
}

• Time Complexity: $O(n)$ - Trong trường hợp xấu nhất, hai con trỏ gặp nhau ở giữa, duyệt hết mảng 1 lần.
• Space Complexity: $O(1)$ - Chỉ dùng 2 biến con trỏ.

Pattern Nhận Diện

Khi mảng đã sắp xếp và cần tìm kiếm cặp phần tử thỏa mãn điều kiện số học (Tổng, Hiệu...), Two Pointers luôn hiệu quả hơn Hash Map về mặt bộ nhớ.