Given an array of unsorted numbers nums and an integer target, find two integers in the array that sum to the target and return their indices.
There are three ways that I know of to solve this problem. Below you’ll find a description of each with some brief code examples. I would like to encourage you to try to implement your own solution first before scrolling down.
Solution 1: Brute Force
The first way, which is the brute force method, is to use nested loops. It tries every possible combination by looping over and take exponential time.
Here’s the example code for that:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
Solution 2: Sorting
Another way of accomplishing this would be to sort the array of numbers in ascending order and then using two pointers start the left at index 0 and the right at the last element. If the current sum is lower increment the left pointer, if the sum is high decrement the right pointer to find the combination that sums to target.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
numbers.sort()
left = 0
right = len(numbers)-1
while (left < right):
cur = numbers[left] + numbers[right]
if (cur == target):
return [left+1, right+1]
elif (cur < target):
left += 1
else:
right -= 1
Solution 3: Hash Table
In the third solution an additional data structure will be utilized to enable finding a solution in O(n) time. Enter the Hash Table, using this it’s possible to subtract the current number from target and check if it’s already a key in the hash table. If it’s not, the original number will be stored as a key with the value equal to its index.
Check out some code examples below: