I have also seen william lin solve it using hash_map in his cses speedrun video on youtube.
But C++ STL unordered_map is a 1 to 1 mapping of key and value. So say x = 12, Now we could make x by doing (a1+a4) + (a2+a3) = 5 + 7. But let's say (a3+a4) = 7 as well , and as unordered_map records only the latest occurrence of 7, so we only have 7 at (a3+a4). As a4 is repeating in both (a1+a4) and (a3+a4), these are not distinct positions and we don't have an answer.
This is not a perfect example, because we can discover other good ways to make 12 if we check other possible combinations. And also a perfect example might not exist given that this is a well-known solution, I just wanted to convey my idea why unordered_map might fail and it is not all clear to me why it actually works for every possibility.
I believe the intuition is exactly that. Map stores the rightmost occurence and you iterate pairs left to right
Let's assume that four numbers that we seek are located in the array as
A.......B.......C......DObviously hashmap is going to store (C+D) and the first pair you discover in the second nested loop is (A+B)
The problem with your example is that we don't actually care about
a1 + a4ifa1 + a2 + a3 + a4 == 12. Yes, this pair maybe fruitless, but we're not even going to reach it. We will first encountera1 + a2and retrievea3 + a4from the hashmap.Thanks for the help. The one fact that we are always going to find $$$(A,B)$$$ first and retrieve $$$(C,D)$$$ covers it. If $$$(C,D)$$$ collides with $$$(A,B)$$$, it never was an answer in the first place. And if there are other pairs colliding with $$$(A,B)$$$ but equal to $$$C+D$$$, they are going to be replaced by $$$(C,D)$$$ in the unordered_map anyway as $$$(C,D)$$$ occurs late.