# Common Hash Table Problem-Solving Approaches in C++: 6 Patterns from the LeetCodeAnimation Repository

> Master common hash table problem-solving approaches in C++. Explore 6 reusable patterns from LeetCodeAnimation to optimize your solutions and reduce time complexity.

- Repository: [吴师兄学算法/LeetCodeAnimation](https://github.com/MisterBooo/LeetCodeAnimation)
- Tags: tutorial
- Published: 2026-03-01

---

**The LeetCodeAnimation repository demonstrates six reusable hash table patterns—complement lookup, frequency counting, pair-sum aggregation, iterator mapping, bit-encoded rolling hash, and trie child maps—that leverage `std::unordered_map` to reduce time complexity from O(N²) or O(N⁴) to O(N) or O(N²) across classic LeetCode problems.**

The MisterBooo/LeetCodeAnimation repository provides animated explanations and C++ implementations for hundreds of LeetCode problems, with hash table techniques appearing as the backbone of optimized solutions. Understanding these common hash table problem-solving approaches allows you to recognize when a problem can be transformed from a brute-force search into a constant-time lookup scenario. This article examines the six foundational patterns implemented in the repository's notes, complete with source file references and production-ready code snippets.

## Complement Lookup Pattern (Two Sum)

The **complement lookup** pattern solves problems requiring you to find pairs that satisfy a specific sum condition. As implemented in `notes/LeetCode第1号问题：两数之和.md`, this approach eliminates the need for nested iteration by storing previously seen values.

While traversing the input array, the algorithm stores each value and its index inside `std::unordered_map<int, int>`. For every new element, it calculates the complement (target minus current value) and checks for its existence in the map. This yields an **O(N) time complexity** with **O(N) space complexity**, a significant improvement over the O(N²) brute-force approach.

```cpp
unordered_map<int,int> record;
for (int i = 0; i < nums.size(); ++i) {
    int complement = target - nums[i];
    if (record.find(complement) != record.end())
        return {i, record[complement]};
    record[nums[i]] = i;
}

```

## Frequency Counter Pattern

The **frequency counter** pattern appears in problems requiring duplicate detection, majority element identification, or vector counting. According to the implementations in `notes/LeetCode第169号问题：求众数.md` and `notes/LeetCode第447号问题：回旋镖的数量.md`, this pattern uses the hash table as a simple accumulator.

Each iteration increments a counter for the encountered key (`freq[x]++`). After population, the map supports O(1) membership queries and statistical scans to identify elements exceeding specific thresholds or matching criteria.

```cpp
unordered_map<int,int> freq;
for (int x : nums) ++freq[x];
for (auto &p : freq)
    if (p.second > 1) /* duplicate logic */

```

## Pair-Sum Aggregation Pattern (4-Sum II)

The **pair-sum aggregation** pattern, demonstrated in `notes/LeetCode第454号问题：四数相加II.md`, solves problems involving matching sums across multiple input arrays. Instead of the naive O(N⁴) quadruple nested loop, this approach uses a two-phase hashing strategy.

Phase one builds a frequency map of all possible sums from arrays A and B (`hashtable[a+b]++`). Phase two iterates through combinations of arrays C and D, looking for the negated sum (`-c-d`) inside the precomputed map. This reduces the complexity to **O(N²) time** and **O(N²) space**.

```cpp
unordered_map<int,int> hashtable;
for (int a : A)
    for (int b : B)
        ++hashtable[a+b];

int res = 0;
for (int c : C)
    for (int d : D)
        if (auto it = hashtable.find(-c-d); it != hashtable.end())
            res += it->second;

```

## Key-to-Iterator Mapping Pattern (LRU Cache)

The **key-to-iterator mapping** pattern enables O(1) operations on data structures with complex ordering requirements. As shown in `notes/LeetCode第146号问题：LRU缓存机制.md`, the LeetCodeAnimation implementation combines a `std::list` for recency tracking with an `std::unordered_map` for direct node access.

The map stores `key → iterator` pairs pointing into the doubly-linked list. The `get` operation uses the map to locate the node instantly, then splices it to the list's front to mark it as recently used. The `put` operation similarly updates both data structures while maintaining the capacity constraint.

```cpp
unordered_map<int, list<pair<int,int>>::iterator> m;
list<pair<int,int>> l;           // most-recent at front

int get(int key) {
    auto it = m.find(key);
    if (it == m.end()) return -1;
    l.splice(l.begin(), l, it->second);
    return it->second->second;
}

```

## Bit-Encoded Rolling Hash Pattern

The **bit-encoded rolling hash** pattern, detailed in `notes/LeetCode第187号问题：重复的DNA序列.md`, demonstrates domain-specific optimization combined with hash tables. To detect repeated 10-letter DNA sequences without storing 10-character strings as keys, the algorithm encodes each nucleotide into 3 bits using its ASCII value's low-three bits.

A rolling 30-bit integer represents the current 10-character window. The hash table stores `m[cur] → count`, allowing O(1) updates per character shift through the string. This achieves **O(N) time complexity** with minimal memory overhead compared to substring storage.

```cpp
int mask = 0x7ffffff, cur = 0;
for (int i = 0; i < 9; ++i) cur = (cur << 3) | (s[i] & 7);
for (int i = 9; i < s.size(); ++i) {
    cur = ((cur & mask) << 3) | (s[i] & 7);
    ++m[cur];                     // unordered_map<int,int> m;
}

```

## Trie with Hash-Map Children Pattern

The **trie with hash-map children** pattern, found in `notes/LeetCode第642号问题：设计一个搜索自动完成系统.md`, replaces the traditional fixed-size array trie node with a dynamic hash table. This provides O(1) child lookup without allocating space for unused character ranges.

Each `TrieNode` contains `unordered_map<char, TrieNode*> child`, mapping characters directly to their child nodes. This structure supports efficient insertion and prefix-based searching, particularly useful for autocomplete systems and dictionary implementations.

```cpp
struct TrieNode {
    bool isWord = false;
    unordered_map<char, TrieNode*> child;   // fast child lookup
};

```

## Architectural Principles Behind These Patterns

Several consistent design principles emerge across the LeetCodeAnimation implementations that explain why these hash table problem-solving approaches prove effective.

**Space-for-Time Trade-off** dominates the repository's strategy. Every pattern deliberately consumes O(N) or O(N²) additional memory to achieve linear or quadratic time complexity rather than polynomial or exponential alternatives.

**Constant-Time Guarantees** from `std::unordered_map` provide the foundation. Average O(1) insertion, lookup, and deletion operations enable the complement search, frequency checks, and iterator retrievals that define these solutions.

**Separation of Concerns** appears in patterns like 4-Sum II, where the algorithm first builds a complete aggregation map before performing any queries. This isolation of preprocessing from search logic improves readability and reusability.

**Domain-Specific Encoding** extends hashing utility beyond direct key storage. The DNA sequence solution demonstrates how bit-level tricks can compress keys before hashing, reducing memory while maintaining the O(1) lookup benefits.

## Summary

- **Complement lookup** stores value-to-index mappings during single-pass iteration to find pairs summing to targets, reducing O(N²) nested loops to O(N) time.
- **Frequency counting** aggregates occurrences using increment operations on `std::unordered_map` to detect duplicates or majority elements in linear time.
- **Pair-sum aggregation** precomputes partial results (like A+B sums) into a frequency table, enabling O(N²) solutions to problems that would otherwise require O(N⁴) iterations.
- **Key-to-iterator mapping** combines hash tables with linked lists to achieve O(1) access and ordering updates simultaneously, essential for LRU cache implementations.
- **Bit-encoded rolling hash** compresses string windows into integers using bitwise operations before hashing, optimizing space for substring pattern detection.
- **Trie child maps** replace array-based trie nodes with `unordered_map<char, TrieNode*>` to provide O(1) character-to-node traversal without fixed allocation overhead.

## Frequently Asked Questions

### What makes `std::unordered_map` the preferred choice for these LeetCode solutions?

`std::unordered_map` provides average-case O(1) time complexity for insertions, deletions, and lookups through hash table implementation. According to the LeetCodeAnimation source code, this constant-time guarantee is essential for transforming exponential or quadratic brute-force algorithms into linear or near-linear solutions. The repository consistently uses this container over `std::map` (which offers O(log N) tree-based operations) when order is not required, maximizing performance for constraint-heavy competitive programming scenarios.

### When should I use the pair-sum aggregation pattern over nested loops?

You should apply the pair-sum aggregation pattern when a problem requires matching sums across multiple independent arrays or lists, such as finding quadruplets from four separate inputs that sum to zero. As demonstrated in `notes/LeetCode第454号问题：四数相加II.md`, this pattern becomes advantageous when the naive approach would require O(N⁴) or higher complexity. By splitting the problem into two O(N²) phases—building a sum-frequency table then querying it—you trade O(N²) space for a dramatic time complexity reduction.

### How does the LRU cache pattern achieve O(1) for both `get` and `put` operations?

The LRU cache achieves O(1) operations through the combination of two data structures: a doubly-linked list maintaining recency order and an `std::unordered_map` storing key-to-iterator mappings. The map provides instant access to any node in the list, while the list allows O(1) removal and front-insertion via `splice` operations. When `get` is called, the map locates the node instantly, and the list updates its position without reallocating or copying elements, as detailed in `notes/LeetCode第146号问题：LRU缓存机制.md`.

### Can these hash table patterns be implemented in other programming languages?

Yes, these patterns are language-agnostic and can be implemented in any language providing hash map or dictionary data structures with O(1) average-case lookups. Python equivalents would use `dict`, Java would use `HashMap`, and JavaScript would use `Map` or plain objects. The LeetCodeAnimation repository uses C++ and `std::unordered_map`, but the algorithmic logic—complement calculations, frequency increments, pair-sum aggregation, and iterator mappings—translates directly to other languages while maintaining the same asymptotic complexity benefits.