在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。
1. 解法1 时间复杂度 O(n^2)
直接两次遍历所有节点,进行求和比较
代码如下:
func twoSum(nums []int, target int) []int {
res := make([]int, 2, 2)
for i:= 0;i<len(nums);i++{
for j:=i+1;j<len(nums);j++{
if nums[i]+nums[j]==target{
res[0] =i
res[1]=j
}
}
}
return res
}
2.解法2: 时间复杂度O(n)
只需要遍历一次所有元素,用 哈希表进行存储即可: 只要数字总和,那么每遍历一次数组,就可以算出他的求和的另一个数字的值,在接下来的遍历中如果找到了就成功得到答案,否则返回Nil
代码如下:
func twoSum(nums []int, target int) []int {
data := make(map[int]int)
for i := 0; i < len(nums); i++ {
another := target - nums[i]
if _, ok := data[another]; ok {
return []int{data[another], i}
}
data[nums[i]]=i
}
return nil
}
语法熟悉
Go多重赋值
if _, ok := m[another]; ok {
首先执行;前的内容,在Go中,根据键访问map会返回两个值,第一个值是这个键对应的值,第二个值是该键是否存在,如果存在返回True,否则False。接下根据OK是否为真判断是否进入后续语句。
return []int{data[another], i }
如果存在,就说明当前位置的元素的另一半存在于这个哈希表中,就访问成功了,那么找到满足要求的两个数,需要返回他俩的下标,这个哈希表中键是元素,值是下标,就返回即可。
标签:哈希,nums,int,Sum,Two,another,表中,Go,data From: https://www.cnblogs.com/CharlseGo/p/18244678如果没有找到另一半,就将这个元素加入到哈希表中,由于是在哈希表中查找,那么哈希表中的元素必然在原Array中位置靠前,所以应先返回哈希表中的元素。