# Two Number Sum (Python & Golang)

Question

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.

Approach 1 – Brute Force

Loop through the array twice to see if any of the combination equal to the sum.

• Time: O (n^2)
• Space: O(1)
``````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 target == nums[i] + nums[j]:
return [i, j]``````
``````func twoSum(nums []int, target int) []int {
for i:=0; i< len(nums)-1; i++ {
for j:=i+1 ; j < len(nums);j++{
if nums[i] + nums[j] == target{
return []int{i,j}
}
}
}

return []int{}
}``````

Approach 2 – Hash Table

Only Loop through the array once. Create a hash-table / dictionary and add each number to the hash-table. Because we know the sum of two number and the current number (ex: i in the loop), we just need to check if (sum – current) is in the hash-table. It is faster , but need more memory than approach 1. We reduce the lookup time from O(n) to O(1), but the space increase from O(1) to O(n)

• Time: O(n)
• Space : O(n)
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i``````
``````func twoSum(nums []int, target int) []int {
hashmap := map[int]int{}
for i, num := range nums{
match := target - num
if j, found := hashmap[match]; found{
return []int{i,j}
}
hashmap[num] = i
}
return []int{}
}``````