给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
在看解法之前,请大家先思考下,自己该怎么解决呢
双重for循环,第一层for循环从下标为0处开始,第二层for循环从下标为1处开始,如果nums[i]+nums[j]== target,那么i和j就是需要返回的下标,这种算法时 间复杂度O(n2),对每个元素,我们都遍历数组中该元素之后剩余的元素是否有与之相加得到的和和目标值匹配,空间复杂度为O(1),在整个过程中没有申请额外的空间
func twoSum(nums []int,target int) []int {
for i:=0;i<len(nums)-1;i++{
for j:=0;j<len(nums);j++{
if nums[i] + nums[j] == target{
return []int{i,j}
}
}
}
return []int{}
}
解法二
上面的解法一有什么问题呢?大家应该都可以看的出来性能问题,那么怎么解决呢?万变不离其中,空间换时间
假定数组 nums = [2, 7, 11, 15], target = 9,假定我们已知数字2,目标值9 ,我们想知道数组中是否有7呢?我们期望有一个方法,入参为7,给我数组中7的下标,那么怎么实现呢?思路是我们把这个数组转换成map<K,V> ,k数组的值,v是值的下标,代码如下,空间复杂度O(n),时间复杂度O(n)
func twoSum(nums []int,target int) []int {
m := make(map[int]int)
for i,v := range nums{
m[v]=i
}
for i:=0;i<len(nums)-1;i++{
temp := target - nums[i]
// i!=v 是防止 3+3,4+4 这种情况,比如下标为0的是3,target是6 那么会返回0,0;同一个下标了
if v,ok :=m[temp]; i!=v &&ok{
return []int{i,v}
}
}
return []int{}
}
解法三
上面的解法而在一开始的时候就把数组的所有元素放入map中,真的需要这样做吗?如果遇到数组中重复数字(哈希冲突)怎么办?我们是否可以边遍历,如果不存在,则把当前数据放入map中,那么循环到下一次的时候,用当前值和以前放入map的值匹配,以此循环。
func twoSum(nums []int, target int) []int {
m := make(map[int]int, len(nums))
res := make([]int, 2)
//遍历数组
for index, value := range nums {
w := target - value
if j, ok := m[w]; ok {
//如果存在
//下标0放入求解值(map存在的和value相加等于target的值)的下标
//下标1放入已知值(value)得下标
res[0] = j
res[1] = index
return res
} else {
//如果不存在,把当前值和下标放入map中
m[value] = index
}
}
return res
}
最后,希望大家有所收获,遇到问题多思考,觉得有帮助的话帮忙分享转发一下,感谢。