LeetCode 热题一之两数之和

本文首发于公众号:Hunter 后端
原文链接:LeetCode热题一之两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
题目来源
此题来源于 LeetCode 题库序号 1。
示例
示例 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]
题解
对于这道题,要在一个数组中找两个元素,使得他们的和为目标值 target,第一反应是需要双重遍历数组,第一重挨个遍历数组元素作为第一个值,第二重是从该元素往后开始遍历作为第二个值,判断这两个值之和是否等于目标值。
其伪代码大致如下:
但是这个操作需要双重遍历数组,其时间复杂度为 n^2,因此,可以寻求一个时间复杂度更小的做法。
我们可以额外建立一个哈希表,key 为元素,value 为元素的索引,每次遍历到的元素 x 可以先查一下哈希表看 target-x 是否存在,存在的话说明我们已经找到了两个目标元素,不存在的话就将元素 x 存入表中。
以下是伪代码:
代码
Python 代码
Golang 代码
版权声明: 本文为 InfoQ 作者【Hunter熊】的原创文章。
原文链接:【http://xie.infoq.cn/article/9b449f020806b9dc0be23e33c】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论