Welcome to this lesson that aims to introduce Hash Tables and Unordered Maps, fundamental concepts in data structures and algorithms. These terms, along with Hash Maps, are often used interchangeably to refer to the same concept. Hash tables, known as unordered_map in C++, are extremely useful constructs that can drastically reduce time complexity while solving certain types of algorithmic problems. They provide an efficient way to maintain a collection of key-value pairs and allow quick access, insertion, and removal operations, making them highly effective in situations where quick lookups are necessary.

In an unordered_map, data is stored based on a generated hash value from a unique key; that way, we can access data quickly by merely knowing the key. For example, if we have a list of integers and a target number, finding two numbers in the list that sum to the target using brute force would require us to compare each number with all the other numbers — a process that would have a quadratic time complexity. However, by using an unordered_map, we can bypass this by storing each number with its index as it arrives and simultaneously checking if the complement (target minus the current number) is already in the unordered_map. This method drastically reduces computational overhead, making it much faster.

Here is what the solution might look like:

C++
Copy to clipboard
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4
5std::vector<int> two_sum(const std::vector<int>& nums, int target) {
6    std::unordered_map<int, int> hash_map;
7    for (int i = 0; i < nums.size(); ++i) {
8        int complement = target - nums[i];
9        if (hash_map.find(complement) != hash_map.end()) {
10            return {hash_map[complement], i};
11        }
12        hash_map[nums[i]] = i;
13    }
14    return {};
15}
16
17// Test
18int main() {
19    std::vector<int> result = two_sum({2, 7, 11, 15}, 9);
20    if (!result.empty()) {
21        std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;  // Output: [0, 1]
22    } else {
23        std::cout << "No solution found" << std::endl;
24    }
25    return 0;
26}

Now that we've sketched a basic understanding of Hash Tables/Unordered Maps/Hash Maps, in the upcoming exercises, we'll dive deeper into the topic. We will practice implementing unordered_map in C++ and solving complex problems faster with this highly efficient data structure. It's quite a powerful tool to have in your algorithmic toolkit, and mastering it will significantly improve your problem-solving skills.