《20190725-两数之和》- 做题笔记

20190725-两数之和

思路分析

1、输入条件 一个元素数组 和 目标值

2、输出返回组成目标值的元素下标

3、另外题目是求数组中两个元素的和等于目标值

4、思考

思维立马定式的想到了双层循环遍历，之后外层循环+内层循环的值等于目标值，就返回外层和内层的下标。

循环注意项

5、其他

1、假如外部输入的数组为空、此场景返回什么？ 【抛出异常】

2、如果没有匹配的元素，此场景返回什么？ 【抛出异常】

方案讲解

官网解答：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2

方法一：暴力法

暴力法很简单，遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素。

方法二：两遍哈希表

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)O(1)。

方法三：一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

方法四：位运算+补码处理 【效率最快】

主体思想还是一样是找当前的差的位置有没有在以前处理过，如果处理过，则返回相应的值。这里巧妙的用了数组，前提是——样本提供的数量有限，不然indexArrayMax还得扩大。

补码介绍：https://baike.baidu.com/item/%E8%A1%A5%E7%A0%81

最快方案解答https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-san-chong-jie-fa-by-looyea

题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

做题答案

最优解