【LeetCode】1. 两数之和

难度

简单

---

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解答

答案1
思路： 传统两层循环依次比较两个数的和即可，但是这种方法性能比较差。

//传统两层循环
func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				return []int{
					i, j,
				}
			}
		}
	}
	return nil
}

提交结果：

• 耗时：24ms
• 内存：3.4MB

答案2
思路：一层循环，依次读取每个num。 当一个num被读取后，就将离Target的差值（target-num）存成Map的key。 这样直到遇到一个num被存储过Map的key的时候。就代表这两个数之和为Target。 这里需要注意的是：如果出现相同的数，则不能覆盖Map的key

//Map反向存储法
func twoSum(nums []int, target int) []int {
	var result []int
	tmp := make(map[int]int, len(nums))

	for index, num := range nums {
		if _, ok := tmp[num]; ok {
			result = []int{
				tmp[num], index,
			}
		}
		if _, ok := tmp[num]; !ok {
			tmp[target-num] = index
		}
	}

	return result
}

提交结果：

• 耗时：4ms
• 内存：4.4MB