没事的时候打算开始玩一玩leetcode,不然天天写代码,却对算法没啥认识还是有点尴尬的。虽说是做题,其实大部分就是为了看看别人牛逼的思路。尽量每天一题把~
1.两数之和
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
第一种方法就是便利数组,随着数组长度增加,执行时间指数型增加。
#时间复杂度:O(n^2)
#空间复杂度:O(1)
func twoSum(nums []int, target int) []int {
for firstIndex,firstNum := range nums{
for secondIndex,secondNum := range nums{
if firstIndex != secondIndex && firstNum + secondNum == target{
return []int{firstIndex, secondIndex}
}
}
}
return nil
}
第二种方式是以空间换时间,把数据存在哈希表里面,最多只用完全遍历一次数组,就能得到结果。
#时间复杂度:O(n)
#空间复杂度:O(n)
func twoSumHash(nums []int, target int) []int {
m := make(map[int]int)
for index,num := range nums{
i,ok := m[target - num]
if ok {
return []int{i,index}
}
m[num] = index
}
return nil
}
题目链接:https://leetcode-cn.com/problems/two-sum/description/
作为脑子是条直线的小白,解题的方法是第一种,打死估计都想不到第二种把。
有疑问加站长微信联系(非本文作者)
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)