侧边栏壁纸
  • 累计撰写 71 篇文章
  • 累计创建 87 个标签
  • 累计收到 5 条评论

目 录CONTENT

文章目录

【LeetCode】1. 两数之和

KunkkaWu
2022-05-16 / 2 评论 / 6 点赞 / 6,045 阅读 / 441 字 / 正在检测是否收录...

难度

简单


题目

给定一个整数数组 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
6

评论区