Các Khái Niệm Cốt Lõi và Ứng Dụng Của Hash Map

1. Bài Toán Trọng Tâm: Tìm kiếm giá trị tương ứng (value) một cách hiệu quả thông qua một khóa duy nhất (key).

2. Tình Huống Thường Gặp:

• Tìm hai số có tổng bằng một giá trị cho trước.
• Xác định phần tử lớn hơn tiếp theo trong một dãy.
• Tìm vị trí xuất hiện đầu tiên hoặc cuối cùng của một ký tự.
• Quản lý bộ nhớ đệm (cache), triển khai LRU (Least Recently Used), hoặc các hệ thống lưu trữ khóa-giá trị.

3. Cấu Trúc Dữ Liệu Phù Hợp: Sử dụng std::unordered_map<KeyType, ValueType> để xây dựng ánh xạ giữa khóa và giá trị.

• KeyType: Kiểu dữ liệu của khóa dùng để tra cứu (ví dụ: số, ký tự).
• ValueType: Thông tin được ánh xạ (ví dụ: chỉ số, giá trị gốc, kết quả tính toán).

4. Mã Giả:

std::unordered_map<Key, Value> map;
for (int i = 0; i < data.size(); ++i) {
    map[data[i]] = some_corresponding_value;
}

Các Bài Toán Minh Họa Với Hash Map

Bài Toán 1: Two Sum (Tổng Hai Số) - LeetCode 1

Ý Tưởng Giải Quyết: Sử dụng std::unordered_map<int, int> để tạo ánh xạ: giá trị → chỉ số.

Quy trình:

1. Duyệt qua mảng.
2. Với mỗi phần tử nums[i], tính giá trị bù: target - nums[i].
3. Kiểm tra xem giá trị bù này đã xuất hiện trong map chưa.
4. Nếu có: trả về {map[complement], i}.
5. Nếu chưa: thêm nums[i] vào map với ánh xạ nums[i] → i.

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> valueToIndex; // key: số, value: chỉ số
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (valueToIndex.count(complement)) {
            return {valueToIndex[complement], i};
        }
        valueToIndex[nums[i]] = i;
    }
    return {};
}

Lưu ý:

• Việc sử dụng dấu ngoặc nhọn {} để khởi tạo std::vector cho phép chuyển đổi ngầm định khi trả về từ hàm. Ví dụ: return {1, 2}; tương đương return std::vector{1, 2};.
• Thao tác map[key] = value sẽ lưu cặp khóa-giá trị (key, value) vào hash table, phục vụ cho việc truy vấn nhanh sau này.

Bài Toán 2: Next Greater Element I (Phần Tử Lớn Hơn Tiếp Theo I) - LeetCode 496

Ý Tưởng Giải Quyết: Kết hợp cấu trúc dữ liệu stack đơn điệu (monotonous stack) và hash map.

Quy trình:

1. Tiền xử lý nums2:
• Sử dụng một stack đơn điệu giảm dần để lưu trữ các phần tử chưa tìm được phần tử lớn hơn tiếp theo.
• Khi gặp một phần tử mới lớn hơn phần tử trên cùng của stack, ta sẽ bật phần tử trên cùng ra khỏi stack và ghi nhận ánh xạ: phần tử bật ra → phần tử hiện tại vào hash map.
• Push phần tử hiện tại vào stack.
2. Truy vấn với nums1: Duyệt qua nums1 và tra cứu kết quả trong hash map đã xây dựng.

Stack Đơn Điệu Giảm Dần: Đảm bảo các phần tử trong stack luôn giảm dần từ đáy lên đỉnh, nghĩa là phần tử trên cùng luôn là phần tử nhỏ nhất.

std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::unordered_map<int, int> nextGreaterMap; // key: phần tử, value: phần tử lớn hơn kế tiếp
    std::stack<int> monoStack; // Stack đơn điệu giảm dần (đỉnh nhỏ nhất)

    // Bước 1: Xây dựng bản đồ ánh xạ từ nums2
    for (int num : nums2) {
        while (!monoStack.empty() && num > monoStack.top()) {
            nextGreaterMap[monoStack.top()] = num;
            monoStack.pop();
        }
        monoStack.push(num);
    }

    // Bước 2: Truy vấn với nums1
    std::vector<int> result;
    for (int num : nums1) {
        if (nextGreaterMap.count(num)) {
            result.push_back(nextGreaterMap[num]);
        } else {
            result.push_back(-1); // Không tìm thấy phần tử lớn hơn
        }
    }
    return result;
}

Ví dụ minh họa với nums2 = {2, 1, 2, 4, 3}:

Bước	Phần tử hiện tại	Trạng thái Stack (Đáy → Đỉnh)	Ánh xạ Hash Map	Ghi chú
1	2	[2]	{}	Stack rỗng, push 2.
2	1	[2, 1]	{}	1 < 2, giữ tính giảm dần, push 1.
3	2	[2] → [2, 2]	{1 → 2}	2 > 1, pop 1, ghi nhận 1 → 2; 2 ≤ 2, push 2.
4	4	[2, 2] → [] → [4]	{1 → 2, 2 → 4}	4 > 2, pop 2, ghi 2 → 4; lặp lại với 2 còn lại, ghi 2 → 4; push 4.
5	3	[4, 3]	{1 → 2, 2 → 4}	3 < 4, push 3.
Kết thúc	-	[4, 3]	{1 → 2, 2 → 4, 3 → -1, 4 → -1}	Các phần tử còn lại trong stack (3, 4) không có phần tử lớn hơn, ánh xạ thành -1.

Bài Toán 3: Isomorphic Strings (Chuỗi Đồng Cấu) - LeetCode 205

Ý Tưởng Giải Quyết: Sử dụng hai hash map để duy trì quan hệ ánh xạ hai chiều: s → t và t → s.

Quy trình:

1. Duyệt qua cả hai chuỗi cùng lúc.
2. Sử dụng mapST để lưu ánh xạ s[i] → t[i].
3. Sử dụng mapTS để lưu ánh xạ ngược t[i] → s[i].
4. Với mỗi cặp ký tự s[i], t[i]:
   • Nếu s[i] đã được ánh xạ nhưng không phải tới t[i], trả về false.
   • Nếu t[i] đã được ánh xạ ngược nhưng không phải tới s[i], trả về false.
   • Nếu không có xung đột, thiết lập ánh xạ mới.
5. Nếu hoàn thành vòng lặp mà không có xung đột, trả về true.

bool isIsomorphic(std::string s, std::string t) {
    std::unordered_map<char, char> mapST;
    std::unordered_map<char, char> mapTS;

    for (int i = 0; i < s.length(); ++i) {
        char charS = s[i], charT = t[i];
        if (mapST.count(charS) && mapST[charS] != charT) return false;
        if (mapTS.count(charT) && mapTS[charT] != charS) return false;

        mapST[charS] = charT;
        mapTS[charT] = charS;
    }
    return true;
}

Các Kỹ Thuật Tiền Tố (Prefix) Kết Hợp Hash Map

1. Bài Toán Trọng Tâm: Ghi lại hoặc kiểm tra sự xuất hiện của một "trạng thái tiền tố" (prefix state) và đếm số lần xuất hiện của nó.

2. Tình Huống Thường Gặp:

• Tổng tiền tố (prefix sum) + hiệu số (ví dụ: bài toán tổng mảng con bằng K).
• Độ dài lớn nhất của mảng con có số lượng 0 và 1 bằng nhau.
• Tổng mảng con chia hết cho K.
• Trạng thái tần suất ký tự tiền tố (sử dụng bitmask hoặc mảng).

3. Cấu Trúc Dữ Liệu Phù Hợp: Sử dụng std::unordered_map<State, Count> hoặc std::unordered_map<State, FirstIndex>.

• State: Trạng thái tiền tố.
• Count: Số lần xuất hiện của trạng thái đó.
• FirstIndex: Chỉ số xuất hiện đầu tiên của trạng thái đó.

4. Mã Giả:

std::unordered_map<int, int> prefixStateCount;
prefixStateCount[initial_state] = 1; // Thường là 1
int currentState = 0;
int result = 0;
for (int num : numbers) {
    currentState = update_state(currentState, num);

    // Truy vấn trạng thái trước đó
    if (prefixStateCount.count(currentState)) {
        result += prefixStateCount[currentState];
    }

    // Cập nhật số lần xuất hiện của trạng thái hiện tại
    prefixStateCount[currentState]++;
}
return result;

Các Bài Toán Minh Họa Với Kỹ Thuật Tiền Tố

Bài Toán 4: Subarray Sum Equals K (Tổng Mảng Con Bằng K) - LeetCode 560

Ý Tưởng Giải Quyết: Sử dụng tổng tiền tố và hash map để đếm số lần xuất hiện của các tổng tiền tố.

Quy trình:

1. Sử dụng std::unordered_map<int, int> prefixSumCount để lưu trữ tần suất xuất hiện của các tổng tiền tố.
2. Khởi tạo prefixSumCount[0] = 1 để xử lý trường hợp mảng con bắt đầu từ đầu mảng.
3. Duyệt qua mảng nums, cập nhật tổng tiền tố hiện tại currentSum.
4. Với mỗi currentSum, kiểm tra xem currentSum - k đã tồn tại trong prefixSumCount chưa. Nếu có, cộng giá trị tương ứng vào kết quả result (vì điều này cho thấy có một mảng con có tổng bằng k).
5. Cập nhật tần suất của currentSum vào prefixSumCount.
6. Trả về result.

int subarraySum(std::vector<int>& nums, int k) {
    std::unordered_map<int, int> prefixSumCount;
    prefixSumCount[0] = 1; // Khởi tạo cho trường hợp mảng con bắt đầu từ đầu

    int currentSum = 0, result = 0;
    for (int num : nums) {
        currentSum += num;

        // Kiểm tra xem có tổng tiền tố nào mà hiệu với currentSum bằng k không
        if (prefixSumCount.count(currentSum - k)) {
            result += prefixSumCount[currentSum - k];
        }

        // Cập nhật tần suất của tổng tiền tố hiện tại
        prefixSumCount[currentSum]++;
    }

    return result;
}

Giải thích prefixSumCount[0] = 1:

Giả sử mảng bắt đầu bằng một số bằng k (ví dụ: nums = {2}, k = 2). Khi duyệt đến phần tử đầu tiên, currentSum = 2. Giá trị cần tìm là currentSum - k = 0. Nếu không khởi tạo prefixSumCount[0] = 1, chúng ta sẽ bỏ sót trường hợp này.

Giải thích result += prefixSumCount[currentSum - k]:

Nếu tại vị trí i, tổng tiền tố là sum_i, và tại một vị trí trước đó j, tổng tiền tố là sum_j, sao cho sum_i - sum_j = k (hay sum_j = sum_i - k), thì mảng con từ j+1 đến i có tổng bằng k. prefixSumCount[currentSum - k] cho biết có bao nhiêu vị trí j trước đó thỏa mãn điều kiện này, mỗi vị trí tương ứng với một mảng con hợp lệ.

Bài Toán 5: Subarrays Divisible by K (Mảng Con Chia Hết Cho K) - LeetCode 974

Ý Tưởng Giải Quyết: Sử dụng tổng tiền tố và phép toán modulo kết hợp với hash map để đếm tần suất các số dư.

Nguyên tắc cốt lõi: Nếu hai tổng tiền tố sum1 và sum2 có cùng số dư khi chia cho k (tức là sum1 % k == sum2 % k), thì hiệu của chúng (là tổng của một mảng con nào đó) sẽ chia hết cho k.

Quy trình:

1. Sử dụng std::unordered_map<int, int> modCount để lưu tần suất xuất hiện của các số dư.
2. Khởi tạo modCount[0] = 1 để xử lý trường hợp mảng con bắt đầu từ đầu có tổng chia hết cho k.
3. Duyệt qua mảng nums, cập nhật tổng tiền tố currentSum.
4. Tính số dư mod = (currentSum % k + k) % k (đảm bảo số dư luôn dương).
5. Nếu mod đã tồn tại trong modCount, nghĩa là có các mảng con có tổng chia hết cho k, cộng giá trị tương ứng vào kết quả result.
6. Cập nhật tần suất của mod vào modCount.
7. Trả về result.

int subarraysDivByK(std::vector<int>& nums, int k) {
    std::unordered_map<int, int> modCount;
    modCount[0] = 1; // Khởi tạo số dư 0 xuất hiện 1 lần

    int currentSum = 0, result = 0;
    for (int num : nums) {
        currentSum += num;

        // Đảm bảo số dư luôn dương trong khoảng [0, k-1]
        int mod = (currentSum % k + k) % k;

        if (modCount.count(mod)) {
            result += modCount[mod];
        }

        modCount[mod]++;
    }

    return result;
}

Ví dụ với nums = {4, 5, 0, -2, -3, 1}, k = 5:

Phần tử	currentSum (Tổng tiền tố)	mod = (currentSum % 5 + 5) % 5	Cập nhật modCount (Ban đầu {0:1})	Kết quả (result)
4	4	4 % 5 = 4	{0:1, 4:1}	0
5	9	9 % 5 = 4	Phát hiện 4 (tần suất 1) -> result += 1. Cập nhật: {0:1, 4:2}	1
0	9	9 % 5 = 4	Phát hiện 4 (tần suất 2) -> result += 2. Cập nhật: {0:1, 4:3}	3
-2	7	7 % 5 = 2	Không phát hiện 2. Cập nhật: {0:1, 2:1, 4:3}	3
-3	4	4 % 5 = 4	Phát hiện 4 (tần suất 3) -> result += 3. Cập nhật: {0:1, 2:1, 4:4}	6
1	5	5 % 5 = 0	Phát hiện 0 (tần suất 1) -> result += 1. Cập nhật: {0:2, 2:1, 4:4}	7

Bài Toán 6: Contiguous Array (Mảng Liên Tục) - LeetCode 525

Ý Tưởng Giải Quyết: Chuyển đổi 0 thành -1, sau đó sử dụng tổng tiền tố và hash map lưu trữ chỉ số xuất hiện đầu tiên của mỗi tổng tiền tố.

Nguyên tắc cốt lõi: Nếu coi 0 là -1 và 1 là +1, thì mảng con có số lượng 0 và 1 bằng nhau sẽ có tổng bằng 0.

Quy trình:

1. Chuyển đổi các phần tử 0 trong mảng thành -1.
2. Sử dụng std::unordered_map<int, int> firstIndex để lưu trữ chỉ số xuất hiện đầu tiên của mỗi tổng tiền tố.
3. Khởi tạo firstIndex[0] = -1 để xử lý trường hợp mảng con hợp lệ bắt đầu từ chỉ số 0.
4. Duyệt qua mảng, cập nhật tổng tiền tố hiện tại currentSum.
5. Nếu currentSum đã tồn tại trong firstIndex, nghĩa là chúng ta tìm thấy một mảng con có tổng bằng 0 (số lượng 0 và 1 bằng nhau). Cập nhật độ dài lớn nhất: maxLen = max(maxLen, currentIndex - firstIndex[currentSum]).
6. Nếu currentSum chưa tồn tại, thêm nó vào firstIndex với chỉ số hiện tại.
7. Trả về maxLen.

int findMaxLength(std::vector<int>& nums) {
    std::unordered_map<int, int> firstIndex;
    firstIndex[0] = -1; // Khởi tạo cho trường hợp mảng con bắt đầu từ index 0

    int currentSum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); ++i) {
        // Chuyển đổi 0 thành -1, 1 giữ nguyên
        currentSum += (nums[i] == 1) ? 1 : -1;

        if (firstIndex.count(currentSum)) {
            // Nếu đã gặp tổng tiền tố này trước đó, tính độ dài mảng con
            maxLen = std::max(maxLen, i - firstIndex[currentSum]);
        } else {
            // Lần đầu tiên gặp tổng tiền tố này, lưu chỉ số
            firstIndex[currentSum] = i;
        }
    }

    return maxLen;
}

Giải thích firstIndex[0] = -1:

Điều này cho phép chúng ta tính đúng độ dài của các mảng con hợp lệ bắt đầu từ chỉ số 0. Ví dụ, nếu mảng là {0, 1} (tương ứng {-1, 1}), tổng tiền tố tại chỉ số 1 là 0. Nếu không có firstIndex[0] = -1, chúng ta sẽ không tính được độ dài là 2.