Two Sum

Intuition

• If there is a value in the future that adds up with the current value to equal target, that number, when subtracted from target, should exist in the rest of the nums array.
• i.e. if you have target - nums in the array, then have your hashmap store as key target - nums[i] and as value i.
• ex) If target - 7 is in your array, and target - 7 = 2, then we return the index of 2 and the index of 7, respectively.
• And ordering does not matter in the sense that if 7 comes after 2, then target - 2 would be stored as a key in the hashmap, and we would find 7 later on in the array.

Runtime

$O(N)$ since you do one pass and hash.

Code

One Pass

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hm = {}
        for i in range(len(nums)):
            if nums[i] in hm:
                return [i, hm[nums[i]]]
            hm[target - nums[i]] = i

Two Passes

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dp = {}
        for i, num in enumerate(nums):
            dp[target - num] = i
        
        for i, num in enumerate(nums):
            if num in dp and dp[num] != i:
                return [i, dp[num]]

Notes

---

References

https://leetcode.com/problems/two-sum/