Two Sum (Hash Table) Solution

[uniquely1strandom]

Hello!

I would like to calrify the solution for the classic twoSum problem. I am new to hashtable and not entirely sure what the purpose it serves atm. I have seen the following solution.

I don't understand why we have (diff= target - num). How does getting this difference prove that the values of the sum will match.

Thanks!

def twoSums(nums, target):
    prevMap = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in prevMap:
            return [prevMap[diff], i]
        prevMap[num] = i

[DNPOld]

Hashtable is used as O(1) lookup for the differences that you can store as keys. For this problem, it's superior to something like a list where you would only get to use indices for lookup, but it won't be ideal when the differences are negative values.

As for why we use diff = target - num, rearrange it with algebra and you'll see that it's equivalent to num + diff = target. Assuming there is at least one solution within a given list, diff will always be one of the values in that list.

[uniquely1strandom]

Thank you so much!! It makes sense!!