题目 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:
Copy 1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解法 解法1 Copy 1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum ( nums [] int , target int ) [] int {
as := make ([] int , 2 )
for i := 0 ; i < len ( nums ); i ++ {
for j := i + 1 ; j < len ( nums ); j ++ {
if nums [ i ] + nums [ j ] == target {
as [ 0 ] = i
as [ 1 ] = j
}
}
}
return as
}
解法2 Copy 1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoSum2 ( nums [] int , target int ) [] int {
r := make ([] int , 2 )
result := make ( map [ int ] int ) //key是nums的值,value是值对应的下标
for n , v := range nums {
if value , ok := result [ target - v ]; ok {
r [ 0 ] = value
r [ 1 ] = n
break
}
result [ v ] = n
}
return r
}
总结 解法1就是最简单的循环相加，时间复杂度是O(n^2)。解法2的话因为题目里面是假设了肯定是有解的，那么就直接用一个循环来完成，时间复杂度使用O(n)
源代码 https://github.com/liguoqinjim/leetcodeGo/tree/master/problems/lab0001