Hash Table is one of the most commonly encountered data structures in LeetCode. In LeetCode, approximately 500+/3000+ problems are officially tagged with "Hash Table".
Hash Table is like a table, you store {key, value} pair in the table like:
| Key | Value |
|---|---|
| key0 | value0 |
| key1 | value1 |
| key2 | value2 |
| ... | ... |
The magic of a Hash Table lies in its ability to quickly ( ) retrieve the associated value when provided with a key! If you're interested in delving deeper into the underlying principles of Hash Tables, you can explore the Hash Table Wikipedia page.
However, If your goal is only to solve LeetCode problems in interviews, most of the time you don't need to deeply understand the underlying principles of Hash Table. You just need to know how to use them appropriately in the right situations.
There are 2 LeetCode problems that ask you to build a hash table
Hash Table can store {key, value} pair. {key, value} pairs have different meanings in different problems!
We use the hash table's key to represent a letter, character, or string, and its value as a boolean to indicate whether the corresponding letter, character, or string has appeared. Thus, for a given element, we can quickly determine whether it exists. You can do the following problems to deepen your understanding of this usage of hash tables. By the way, many languages have built-in hash sets (C++: unordered_set, Java: HashSet, etc.) to solve this kind of problems.
We use the hash table's key to represent a letter, character, or string, and its value as an integer to indicate the number of times the corresponding letter, character, or string has appeared. Thus, for a given element, we can quickly determine the number of times it has already appeared. You can do the following problems to deepen your understanding of this usage of hash tables.
767 is a little bit more challenging
In some problems, the use of hash tables can be more flexible. For instance, hash tables can be used to record the number of elements in a sequence. The following two problems are examples of this approach.
The key is the prefix sum, and the value is the number of times this prefix sum occurs. Problem 560 is a classic example of this.
The key is the remainder of the prefix sum, and the value is the number of times this remainder occurs. The following two problems utilize this method.
If there are space complexity constraints in the problem, then you can consider using the existing array as a hash table.