Problem
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
example
1
2
3
4
|
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
|
Solution
Brute force
1
2
3
4
5
6
7
8
9
10
|
func twoSum(nums []int, target int) []int {
for idx := 0;idx<len(nums)-1;idx++ {
for jdx:=idx+1;jdx<len(nums);jdx++{
if nums[idx]+nums[jdx]==target {
return []int{idx,jdx}
}
}
}
return []int{}
}
|
Hash map
1
2
3
4
5
6
7
8
9
10
11
12
|
func twoSum(nums []int, target int) []int {
q := make(map[int]int,len(nums))
for idx:=range nums {
add := target - nums[idx]
if _, ok := q[add]; ok {
return []int{idx, q[add]}
}
q[nums[idx]] = idx
}
return []int{}
}
|