Bài toán Two Sum

Cho một mảng các số nguyên nums và một số nguyên target. Yêu cầu là tìm hai số trong mảng có tổng bằng target và trả về các chỉ số (index) của chúng.

Bạn có thể giả định rằng mỗi đầu vào chỉ có một lời giải duy nhất, và bạn không được sử dụng cùng một phần tử hai lần. Thứ tự trả về các chỉ số không quan trọng.

Ví dụ:

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

Ví dụ 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Ví dụ 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Ràng buộc:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Chỉ có một đáp án hợp lệ duy nhất.

Phương pháp giải quyết bằng Bảng Băm (Hash Map)

Một cách tiếp cận đơn giản để giải quyết bài toán này là sử dụng hai vòng lặp lồng nhau (brute-force), kiểm tra tất cả các cặp số có thể. Tuy nhiên, phương pháp này có độ phức tạp thời gian là O(n^2), không hiệu quả đối với các mảng lớn. Để cải thiện hiệu suất, chúng ta có thể tận dụng cấu trúc dữ liệu bảng băm (hash map).

Tại sao sử dụng Bảng Băm?

Bảng băm cho phép chúng ta thực hiện các thao tác tìm kiếm, thêm và xóa trong thời gian trung bình là O(1). Điều này cực kỳ hữu ích khi chúng ta cần nhanh chóng kiểm tra xem một giá trị nào đó đã xuất hiện trước đây hay chưa.

Thuật toán:

1. Khởi tạo một bảng băm (ví dụ: unordered_map trong C++, HashMap trong Java, dict trong Python) để lưu trữ các số đã duyệt qua cùng với chỉ số của chúng. Key sẽ là giá trị số và Value sẽ là chỉ số của nó trong mảng.
2. Duyệt qua từng phần tử nums[i] trong mảng nums từ trái sang phải.
3. Đối với mỗi phần tử nums[i], tính toán giá trị "bổ sung" cần thiết để đạt được target: soCanTim = target - nums[i].
4. Kiểm tra xem soCanTim đã tồn tại trong bảng băm hay chưa.
   • Nếu soCanTim đã có trong bảng băm, điều đó có nghĩa là chúng ta đã tìm thấy cặp số có tổng bằng target. Chỉ số của soCanTim sẽ là giá trị tương ứng trong bảng băm, và chỉ số thứ hai là i (chỉ số của phần tử hiện tại). Trả về cặp chỉ số này.
   • Nếu soCanTim chưa có trong bảng băm, thêm phần tử hiện tại nums[i] cùng với chỉ số i của nó vào bảng băm.
5. Nếu sau khi duyệt hết mảng mà không tìm thấy cặp số nào, trả về một mảng rỗng (hoặc xử lý lỗi tùy theo yêu cầu). Do ràng buộc bài toán đảm bảo luôn có một đáp án, bước này thường không cần thiết trong các giải pháp thực tế cho bài toán LeetCode này.

Cách tiếp cận này giúp giảm độ phức tạp thời gian xuống O(n) vì chúng ta chỉ cần duyệt qua mảng một lần, và mỗi thao tác tra cứu/thêm vào bảng băm mất thời gian trung bình là O(1).

Cài đặt bằng các ngôn ngữ lập trình

C++

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& danhSachSo, int giaTriMucTieu) {
        // Khởi tạo một unordered_map để lưu trữ các số đã duyệt và chỉ số của chúng.
        // Key: giá trị của số, Value: chỉ số của số đó.
        std::unordered_map<int, int> banDoChiSo; 

        // Duyệt qua từng phần tử trong danh sách số
        for (int chiSoHienTai = 0; chiSoHienTai < danhSachSo.size(); ++chiSoHienTai) {
            int soHienTai = danhSachSo[chiSoHienTai];
            // Tính toán giá trị cần tìm để tổng bằng giaTriMucTieu
            int soCanTimBoSung = giaTriMucTieu - soHienTai;

            // Kiểm tra xem soCanTimBoSung đã có trong bản đồ chưa
            // Nếu có, tức là chúng ta đã tìm thấy cặp số
            if (banDoChiSo.count(soCanTimBoSung)) {
                // Trả về chỉ số của soCanTimBoSung (lấy từ bản đồ) và chỉ số hiện tại
                return { banDoChiSo[soCanTimBoSung], chiSoHienTai };
            }

            // Nếu chưa tìm thấy soCanTimBoSung, thêm số hiện tại và chỉ số của nó vào bản đồ
            banDoChiSo[soHienTai] = chiSoHienTai;
        }

        // Theo yêu cầu bài toán LeetCode, luôn có một đáp án.
        // Tuy nhiên, trong trường hợp tổng quát, chúng ta có thể trả về mảng rỗng nếu không tìm thấy.
        return {}; 
    }
};

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /**
     * Tìm hai chỉ số của các số trong mảng có tổng bằng giá trị mục tiêu.
     * Sử dụng cấu trúc dữ liệu bảng băm (HashMap) để đạt hiệu suất tối ưu O(n).
     *
     * @param cacSo Mảng các số nguyên.
     * @param tongMongMuon Giá trị mục tiêu mà tổng của hai số phải đạt được.
     * @return Một mảng chứa hai chỉ số của các số tìm được, hoặc mảng rỗng nếu không có cặp nào (trong trường hợp tổng quát).
     */
    public int[] twoSum(int[] cacSo, int tongMongMuon) {
        // Khởi tạo một HashMap để lưu trữ các giá trị số và chỉ số của chúng.
        // Key: giá trị số, Value: chỉ số trong mảng.
        Map<Integer, Integer> banDoChiSo = new HashMap<>(); 

        // Duyệt qua mảng các số
        for (int chiSoHienTai = 0; chiSoHienTai < cacSo.length; chiSoHienTai++) {
            int soHienTai = cacSo[chiSoHienTai];
            // Tính toán giá trị còn lại cần tìm
            int giaTriConLai = tongMongMuon - soHienTai;

            // Kiểm tra xem giaTriConLai đã có trong bản đồ chưa.
            // Nếu có, tức là đã tìm thấy cặp số.
            if (banDoChiSo.containsKey(giaTriConLai)) {
                // Trả về chỉ số của giaTriConLai (lấy từ bản đồ) và chỉ số hiện tại.
                return new int[] { banDoChiSo.get(giaTriConLai), chiSoHienTai };
            }

            // Nếu chưa tìm thấy giaTriConLai, thêm số hiện tại và chỉ số của nó vào bản đồ.
            banDoChiSo.put(soHienTai, chiSoHienTai);
        }

        // Theo đề bài, luôn có một đáp án. Nếu không, có thể trả về mảng rỗng.
        return new int[0]; 
    }
}

Python

class Solution:
    def twoSum(self, danh_sach_so: list[int], tong_muc_tieu: int) -> list[int]:
        """
        Tìm hai chỉ số của các số trong danh sách có tổng bằng giá trị mục tiêu.
        Sử dụng bảng băm (hash map hay dictionary trong Python) để tối ưu hóa việc tìm kiếm.

        :param danh_sach_so: Danh sách các số nguyên.
        :param tong_muc_tieu: Giá trị tổng mong muốn.
        :return: Một danh sách chứa hai chỉ số tìm được.
        """
        # Khởi tạo một dictionary để lưu trữ các số đã duyệt và chỉ số của chúng.
        # Key: giá trị số, Value: chỉ số của số đó.
        map_cac_so_da_thay = {} 

        # Duyệt qua danh sách số cùng với chỉ số của từng phần tử
        for chi_so_hien_tai, so_hien_tai in enumerate(danh_sach_so):
            # Tính toán số bổ sung cần thiết để đạt được tổng_muc_tieu
            so_bo_sung_can_tim = tong_muc_tieu - so_hien_tai

            # Kiểm tra xem so_bo_sung_can_tim đã tồn tại trong dictionary chưa.
            # Nếu có, tức là chúng ta đã tìm thấy cặp số.
            if so_bo_sung_can_tim in map_cac_so_da_thay:
                # Trả về chỉ số của so_bo_sung_can_tim (lấy từ dictionary) và chỉ số hiện tại.
                return [map_cac_so_da_thay[so_bo_sung_can_tim], chi_so_hien_tai]
            
            # Nếu chưa tìm thấy, thêm số hiện tại và chỉ số của nó vào dictionary.
            map_cac_so_da_thay[so_hien_tai] = chi_so_hien_tai
        
        # Theo ràng buộc của bài toán LeetCode, luôn có một đáp án hợp lệ.
        # Trong trường hợp tổng quát, nếu không tìm thấy cặp nào, có thể trả về một danh sách rỗng.
        return []