I think 2-sum is a pretty common starting point when people learn about the existence of Leetcode and similar websites. Personally, I don't think questions like these are good indicators of how good a programmer someone is, but for whatever reason, every company likes to ask these styles of questions in interviews.
With that being said, this is probably one of the more likable questions in my opinion. It's a good example of a question where there's a very obvious brute force answer in a poor time complexity (that would probably be used if you've never done any of these problems before) and a clever way to use space to get a better time complexity. (namely, not having to check every combination of numbers possible)
The solution on Leetcode doesn't give a visualization of what they're doing, so I went ahead and made a graphic that details the general idea of what their solution is. I don't think I'm going to go into nitty-gritty code solutions, but rather a general idea of how to understand solution articles and other users' solution submissions. This article is probably best utilized if you have some background programming experience.
The jist of this problem is basically given some target number and an unsorted array of numbers, find the pair of numbers that sum up to our target.
For the sake of brevity, I'm not going to consider the sorted case and the 2-pointers method: I'll save that for when I make a post on 3-Sum. If that made no sense, don't worry about it for now.
Let's consider the array [4,3,5,12,7,1,9].
For small arrays/small numbers, it's generally pretty easy to find the answer for any target.
For example, if our target was 19, it's pretty obvious which 2 numbers sum to 19, that being 12 and 7.
Thus, our solution for this would be [3,4] (representing the indicies of our solutions).
The naive solution should be quite easy to understand: simply try out every possible pair of numbers until we get our target.
One implementation of this idea would be to start with 4, then check 3, 5, 12, 7, 1, 9, and then iterate to 3, and check 5, 12, 7, 1, 9, then to 5 and check 12, 7, 1, 9, and so on.
This solution is obviously very inefficient and slow -- there has to be a better way than checking every possible pair. We loop over each element (which is O(n)) and then within each iteration, loop over the remaining elements (which is also O(n)). Thus, our time complexity is O(n^2). Can we do better?
Let's start with our first element '4' and ask ourselves what implications would there be is 4 was a solution.
If 4 was part of the solution pair, then it would mean that there must exist 15 somewhere
else in the array, since 15 + 4 = 19. That is to say, 15 and 4 are complements of one another.
In our example array, 12 and 7 is the pair that sums to 19 and are thus complements of one another.
We can use the idea of checking only for complements to speed up our solution.
Instead of checking every combination, it's enough to check if the array contains an element and its complement. That is, everytime we iterate through
the array and consider some element, we only need to check if the complement also exists.
Going back to our example, when we consider the element '3', we only have to see if its complement (16) exists in the array. It doesn't,
so it obviously can't be part of the solution. However, once we reach the element '7,' we check to see if its complement (12) exists. It does,
so 12 and 7 must be our solution.
We can reduce the time of checking for a complement to O(1) with a hashtable. (lookup for a hashtable is treated as O(1)).
This is how we can reduce our solution to O(n).
We introduce a hash table to keep track of what elements we have seen (and thus know to exist). Since at the start we haven't seen any numbers, the hash table is blank, and we assume nothing about the existence of a element's complement.
Start with our first element 4 -- 4's complement (15) is not in our hashtable (so for now we assume it doesn't exist), so we don't have our solution. We have now seen the #4 and need to record that, so we insert it into our hash table.
Now we go to 3 -- again, 3's complement (16) is not in our hashtable. we have now seen 3 and record that, so we insert it into our hash table.
Now we go to 5 -- it's complement is 14 and isn't in the hashtable. We record 5 and keep going.
We go to 12 -- 12's complement is 7 and 7 isn't in our hashtable. Remember, even though we personally know 7 is in our array, the computer hasn't seen it yet (so to the computer, it doesn't exist yet). We don't have a solution yet, so we record it in our hashtable and keep going.
We go to 7. 7's complement is 12, and we (and the computer) have seen 12 before (it's in our hashtable). Because of this, we now have our solution and we didn't have to check every combination. We now know the solution are the array indicies of 7 and 12.
So hopefully this makes it easier to understand what the Leetcode solution was talking about. This hashtable uses O(n) space since it contains a max of n elements. We also have to only iterate through our array once, so our runtime is now O(n). (which is much better than O(n^2)).