本题的链接:BM50 两数之和
最初拿到这个题目首先想到的就是两个指针,然后向后遍历,于是写出来的代码也简明易懂:
package main
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
func twoSum(numbers []int, target int) []int {
// write code here
for i := 0; i < len(numbers)-1; i++ {
for j := i + 1; j < len(numbers); j++ {
if numbers[i]+numbers[j] == target {
return []int{i + 1, j + 1}
}
}
}
return []int{}
}
然而很不幸的是这个解法超时了。如果数组特别大,那么这个解法显然是不占优势的,时间复杂度明显是O(n^2),而题目要求的时间复杂度是O(nlogn)。此时,如果引入一个map,则可以将对数组的遍历降低成一趟,从而提升时间效率。
package main
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
func twoSum(numbers []int, target int) []int {
// write code here
var m = make(map[int]int)
for i := 0; i < len(numbers); i++ {
v, ok := m[target-numbers[i]]
if ok {
return []int{v + 1, i + 1}
} else {
m[numbers[i]] = i
}
}
return []int{}
}
这样一来,整个用例的测试时间不过62ms。时间复杂度也降低到了O(n)
标签:return,target,BM50,牛客,int,numbers,数组,两数,整型 From: https://www.cnblogs.com/wingsless/p/17107463.html