Two Sum (求2个数的和)

最近在LeetCode 上抽空做做题,顺便记录一下解题思路。

问题

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

给定一个整数数组,返回两个数字的索引,使它们相加到一个特定的目标。
您可以假设每个输入都只有一个解决方案,而您可能不会使用相同的元素两次。

问题的例子

问题解析

给定一个数组 和 特定的目标值,返回数组中2个数字相加 和等于目标的数组下标。

解题思路

可能许多人第一方案就是使用双重for循环来解决,当然,这个方案完全可以解决该问题。(我后来在公司面试中问过一次该问题,当时应聘者给出的方案也是此方案)
平时在刷LeetCode的时候,解决思路就是先想出一种解决方案,实现以后在去思考优化方案。

使用双重for 循环实现

该方法虽然解决了问题,但是该方法运行时间较长,时间复杂度跟冒泡算法一致 O2,且在众多实现方案中运行时间在43.3%,如下图:
《Two Sum (求2个数的和)》

优化

虽然问题解决了,但是需要考虑最优的算法,双重循环时间复杂度较高,如果使用一次循环,比较俩值相加是否等于目标值,使用到Map 结构,用key value 存储值和数组下标,这样每次循环只需要判断 目标值 – 当前值 = 差值,差值在Map 中即找到结果,具体代码如下:

该方案只实现一次循环,即可计算出答案,运行时间在7ms,排名93.02%,如下:
《Two Sum (求2个数的和)》

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注