Classic Hash Tricks: Two Sum and Friends

Two Sum

Find two positions in an unsorted vector whose numbers add to a target. For each number x, the partner needed is target - x. Remember every number seen so far (number → index):

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 7, 11, 15};
    int target = 9;
    unordered_map<int, int> seen;          // number -> index
    for (int i = 0; i < (int)v.size(); i++) {
        auto it = seen.find(target - v[i]);
        if (it != seen.end()) {
            cout << it->second << " " << i << endl;
            break;
        }
        seen[v[i]] = i;
    }
    return 0;
}

Output

0 1

Think of it like this: At a party you need someone with a matching shirt. Instead of asking everyone each time a person arrives, you keep a guest book of colours already in the room.

find() returns end() when the key isn't there. Prefer it (or count()) over seen[key] for checking, because [] would add the key.

Grouping by a key

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    map<string, vector<string>> groups;
    for (const string& w : words) {
        string key = w;
        sort(key.begin(), key.end());       // anagrams share the same sorted letters
        groups[key].push_back(w);
    }
    for (auto& [key, list] : groups) {
        cout << key << ":";
        for (auto& w : list) cout << ' ' << w;
        cout << endl;
    }
    return 0;
}

Output

abt: bat
aet: eat tea ate
ant: tan nat

Remember: If you're writing a loop inside a loop just to find something, ask: could a hash map remember it for me?