LeetCode_1_50

发表于 | 分类于

emmm，老老实实刷题吧，加油~。拟每篇记录50道算法题，分别用python 和 Golang 实现。

1 Two Sum

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

思路

两层循环，最坏需要 （n-1）+ (n-2) + … + 3 + 2 + 1 次循环。也就是n(n-1)/2次。
但是从后面运行的效率来看，这种思路并不好。参考下其他解法，说只循环一次，但是让一个字典记录下已经循环的元素，直到循环到某个元素，它和字典里记录下的某个元素满足条件。

solution by Python

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], tartget: int) -> List[int]:
        prev_dic = {}
        for index, item in enumerate(nums):
            if target - item in prev_dic:
                return [index, prev_dic[target-item]]
            prev_dic[item] = index

我尝试去写下golang 的解法，发现自己不会。咦，好弱啊。抄下其他人的。

1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(nums []int, target int) []int {
	valueStore := make(map[int]int)
	var result []int
	for i:=0; i < len(nums); i++ {
		if value, ok :=valueStore[target - nums[i]]; ok {
			result = append(result, value, i)
			return result
		}
		valueStore[nums[i]] = i 
	}
	return result
}

上传，看了下结果，我震惊了。同样的思路，go实现起来，无论时间维度还是空间维度，都碾压python。赶紧去练习一波golang。