关于LeetCode两数之和解法中unordered_map.find()的工作原理问询

Hey there! Let's clear up your confusion about how the unordered_map works in that 2Sum optimal code—this is a common point of confusion when first working with C++ STL containers, so you're not alone.

1. Why hashTable.find(diff) works even without explicit initialization #

In C++, when you declare an unordered_map<int, int> hashTable; without any explicit initialization, the default constructor of unordered_map automatically creates an empty but fully valid container. It's not "uninitialized" in the broken sense—think of it as an empty dictionary ready to store key-value pairs.

The find() method is a built-in member function of unordered_map that works perfectly on empty containers: it simply checks if the key diff exists. Since the container is empty, it will return the end() iterator (a special iterator that points just past the last element of the container, indicating no match was found).

2. The logic behind the if condition #

Let's look at the typical 2Sum optimal code to make this concrete:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hashTable;
    for (int i = 0; i < nums.size(); ++i) {
        int diff = target - nums[i];
        auto found = hashTable.find(diff);
        // Check if we found a matching key
        if (found != hashTable.end()) {
            // Return the index of the found element and current index
            return {found->second, i};
        }
        // If not found, add current element and its index to the map
        hashTable[nums[i]] = i;
    }
    return {}; // No solution found (per problem constraints, this won't run)
}

The if (found != hashTable.end()) condition is checking whether the find() operation actually located the key diff:

• If found equals hashTable.end(), that means diff wasn't present in the map (so we haven't seen a number that adds up to target with the current number yet).
• If found does not equal hashTable.end(), then found points to a valid key-value pair in the map: found->first is the number we're looking for, and found->second is its index in the input array.

3. Why your iterator print shows an empty map #

When you tried printing the iterator right after find(diff) in the first loop iteration, the map is indeed empty—we haven't added any elements to it yet! The magic happens in subsequent loop iterations:

• After the first find() fails, we add nums[0] and its index 0 to the map.
• In the second iteration, we calculate diff = target - nums[1], then find() checks the map (which now has one entry) for that diff. If it's present, we return the indices; if not, we add nums[1] and index 1 to the map, and so on.

So the map starts empty, but it gets populated as we iterate through the array—each find() checks only the elements we've already processed, which is exactly what we need for the 2Sum solution (since we don't want to reuse the same element twice).

内容的提问来源于stack exchange，提问作者user9275416