Hash maps

Use a hash map when your loop keeps asking about things it has already seen: whether a value appeared, how often, at which index, or the best value tied to a key. Work out the key from the question. Two Sum looks up each number's partner. Anagrams use letter counts as the key. Counting subarrays with a given sum looks up an earlier prefix sum.

For Two Sum, go left to right. Before index i, the hash map holds an index for every value before i. Look up the partner before you add the current value, so a number can't pair with itself. Repeated values are fine: with target 6, [3, 3] uses two different positions.

pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    use std::collections::HashMap;
    let mut seen = HashMap::<i64, usize>::new();
    for (i, &x) in nums.iter().enumerate() {
        let x = i64::from(x);
        if let Some(&j) = seen.get(&(i64::from(target) - x)) {
            return Some((j, i));
        }
        seen.insert(x, i);
    }
    None
}

Hash map lookups take O(1) time on average, so this takes O(n) time and O(n) space. Converting to i64 before subtracting avoids overflow. When a value repeats, the map overwrites its older index, which is fine here because any earlier copy works. But if you wanted the longest matching range, you'd need the earliest index, so overwriting would be wrong.

What changes the method: returning all pairs changes the output size and how you handle duplicates. Returning a count needs frequencies. Keeping the original order can rule out sorting. If the key is a string of length m, building and hashing it costs O(m).

To group anagrams of lowercase English words, use a tuple of 26 letter counts as the key. Order doesn't matter, but counts do: a set of letters would treat "abb" and "ab" as the same. For other characters, decide on the key explicitly.

Practice: LC 1 Two Sum, LC 242 Valid Anagram, LC 49 Group Anagrams, LC 128 Longest Consecutive Sequence. In the last one, only start counting a run at a value whose predecessor isn't in the set. Otherwise you rescan the same runs, and it can become O(n²).

Check your understanding: What can the hash map safely forget? Why look up before you insert? What changes when the question asks for the earliest, latest, longest, or total count?