LeetCode刷题Day1:两数之和

从今天开始,把LeetCode刷题作为每天日常计划的一项。尽早做准备,同时也每天对算法和相关的技能知识通过刷题的形式进行潜移默化的提升和加深理解。其实身边已经有很多程序猿朋友都在LeetCode刷题了,再不参与进来,都要出圈儿了呀。

今天是Day1,从第一道题目开始:
 


两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 

示例: 

给定 nums = [2, 7, 11, 15], target = 9 

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
 


 
思路一:暴力遍历

也是最简单最原始的未经优化的方案思路。

首先明确题目要求,可以假设每种输入只会对应一个答案,即一定会有且只有一对符合要求的数据。

所以得到数组的长度,然后从第一个开始进行循环,将目标值target减去当前被循环的值,得到与之可以配对的值,然后在数组中进行寻找,如果找到,就返回2个符合要求的值的索引,否则继续下一次寻找,直到找到。

最外层循环的条件中 x&y异或之后如果为1,说明已经找到对应的结果,就不再循环。时间复杂度是O(n²),空间复杂度是O(1)。

func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int

for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}

}

return []int{x,y}
}

思路二:进一步提升效率,可以利用哈希表
从第一个思路中,可以看到其实在判断一个值在一个“表”中是否存在的时候,我们采用了遍历的方式,这样的话时间复杂度就是O(n),但是大家肯定都知道,哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以,这样思路就很清晰了,我们需要先把传过来的数组生成对应的哈希结构,也就是Go里面的map字典,这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key,index作为map的value。代码实现如下。
 

func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int

//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}

for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}

}

return []int{x,y}
}

今天这道题的难度级别是简单,但是带我回顾了Go语言的数组、map的相关知识和用法,以及哈希表这一知识点。

0 个评论

要回复文章请先登录注册