[LeetCode] Two Sum

 

 

Problem

 

 

 

 

 

 

 

---

 

Solution

 

Could use nested for-loops but that will end up with O(n^2) complexity. Arrays have constant complexity when accessing a known index. However arrays can have up to O(n) complexity when searching while hashmap has near constant complexity.

 

In order to improve the speed, make a hashmap by mapping each element in nums to its index number. 

 

When iterating through the array, get the complement of target and current number.

If the complement exists in the hashmap as a key, return current position and the value(the index for nums) of the key.

If the complement does not exist in the hashmap, add current number as a key and current index as the value.

 

 

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        hashmap = {}
        for i in range(len(nums)):
            diff = target - nums[i]
            if diff in hashmap:
                return [hashmap[diff], i]
            hashmap[nums[i]] = i