1. Two Sum
On This Page
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Topics: array, hash table
If we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
First accepted
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_set = set(nums) # to search in a O(1)
while nums:
n1 = nums.pop() # get last
n2 = target - n1
if n1 == n2:
if n2 in nums:
return [len(nums), nums.index(n2)]
elif n2 in nums_set:
return [len(nums), nums.index(n2)]
- faster than 64.51%
- Memory Usage: 15.5 MB, less than 9.15%
Time complexity:
- set(nums): O(n)
- while nums: O(n)
- nums.pop: O(1)
- nums.index: O(n)
Better solution
remember indexes of “passed”
n's
fromnums
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for idx, n1 in enumerate(nums):
n2 = target - n1
if n2 in hashmap:
return [idx, hashmap[n2]]
hashmap[n1] = idx
- faster than 53.00%
- Memory Usage: 15.1 MB, less than 52.14%