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{}
}