1. Two Sum
Approach 1: Store value, index pairs
class Solution(object):
def twoSum(self, nums, target):
"""
https://leetcode.com/problems/two-sum/description/
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
di = {}
for i in range(len(nums)):
if target - nums[i] in di:
return [di[target - nums[i]], i]
else:
di[nums[i]] = i
For each of the numbers in the array, store their value and index in a hash table, and every time, check if target-nums[i]
exists in the hash table already. If yes we can return the indices of both these values.
Time Complexity: O(N), where N = len(nums)
Space Complexity: O(N), where N = len(nums)
Last updated