Given an array of integers and a target, return the indexes of the values that add up to the target.
// inputArr := [3,2,4]
// target := 6
// output := myFunction(inputArr, windowSize)
// output = [1,2]
In the simple approach, we can walkthrough the array in a nested loop and for each element, check if there's another element that adds up to the target.
func twoSumSimple(input []int, target int) []int{
for i:=0; i<len(input); i++{
for j := i+1 ; j <len(input); j++{
if input[i] + input[j] == target{
return []int{i, j}
}
}
}
}
With the previous approach, we have O(n^2) runtime, since we essentially loop through every remaining item for every item. We can do better by keeping track of the visited items. For each item in the list, we need to be able to quickly lookup if we have seen another item that complements the current one. Since we need efficient lookups, we can use a hashtable. Golang has the builtin map data structure that fits this purpose.
So now, the algorithm becomes:
With this approach, we only have to do N lookups and N inserts in to the table, each of which will cost O(1) time with the map data structure.
func twoSum(nums []int, target int) []int {
targetSet := map[int]int{}
var complement int
for i, v := range nums {
complement = target - v
if found, ok := targetSet[v]; ok {
return []int{found, i}
}
targetSet[complement] = i
}
return nil
}
You can try it yourself on leetcode
Please comment or dm me if you have other questions or remarks.
Until next time,
Stay all in!
Reha S.
Sep 09 2022