一、两数之和
题目：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这道题目比较容易想到的是通过暴力搜索求解，但暴力搜索的时间复杂度为 O(n^2)。如果使用哈希的思想，利用Python中list的查询方式，我们可以将复杂度降低到 O(n)。有两个值得注意的地方：1同样的元素不能重复使用（也就是不能自己加自己）2给定的数组中可能有相同的元素（比如 [3, 3, 4, 4, 5]）
方法一：
暴力搜索，但是超时间：
暴力搜索
方法二：
考虑（taget-nums[i])也在nums里：
执行通过，不过耗时较长。
进一步优化解法。想着，num2的查找并不需要每次从 nums 查找一遍，只需要从 num1 位置之前或之后查找即可。但为了方便 index 这里选择从 num1 位置之前查找：
优化后的
方法三：
参考了大神们的解法，通过哈希来求解，这里通过字典来模拟哈希查询的过程。
个人理解这种办法相较于方法一其实就是字典记录了num1和 num2 的值和位置，而省了再查找 num2 索引的步骤。
通过字典的方法，查找效率快很多，执行速度大幅缩短。
网友评论