2.1　两数之和

我们先拿最基础的加法运算来入门。两数之和是一道很简单的题目，作为力扣（LeetCode）上的第一个问题，相信它是大多数人刷题的起点。

题目描述（第1题）

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的索引值。你可以假设每种输入只会对应一个答案，但是，你不能重复利用这个数组中同样的元素。

示例

给定 nums=[2,7,11,15]，target=9

因为 nums[0]+nums[1]=2+7=9，所以返回[0,1]

解法一　排序+双指针（不符合题意）

思路

首先想到的最简单粗暴的方法是，使用两层循环找出所有的两两组合，逐个判断其和是否等于target，如果相等则直接返回。暴力解法的时间复杂度是O(n2)，空间复杂度是O(1)，平方阶意味着算法效率不高，不妨尝试一下别的方法。

可以先对数组进行一次排序，不妨采用升序，这样就可以使用双指针中的头/尾指针法来解决这个问题了。以题目中的[2,7,11,15]为例，由于数组本身就是有序的，经过一次升序排序不会发生变化。之后建立头/尾指针，分别指向2和15，将两者相加即2+15=17，得到17。

17大于目标值9，由于数组是升序的，因此需要将尾指针向前移动，这样加起来的值才可能变小。经过一次移动之后，头/尾指针分别指向2和11，此时2+11=13。

13还是大于目标值9，因此尾指针继续前移，现在头/尾指针分别指向2和7。

将其相加，2+7=9，发现正是要找的数，于是返回其对应的索引值[0,1]。

总结一下，在进行一次升序排序后，分别取首/尾元素，即最小值和最大值，如果相加大于 target，那么较大的数和其他所有的数相加的结果就没有必要看了，肯定都不满足，向前移动一下尾指针将其剔除。按照这样的逻辑继续执行，直到找到满足条件的数的组合。

代码

复杂度分析

●　时间复杂度：算法瓶颈在于排序，因此时间复杂度为O(nlogn)，其中n为数组长度。

●　空间复杂度：不确定，取决于内部排序算法的具体实现。

上面的解法是有缺陷的，因为排序会导致原数组的索引发生变化，在本题要求下这种方法是不可取的（如果仍然想用排序法解决，可以将索引值作为第二维信息保存）。不过发散思维、多做尝试是正确的，对之后做题会有帮助，将来碰到类似的问题时也能够很快提取到这些信息。另外，这种算法的时间复杂度是O(nlogn)，时间复杂度并不是很好，那么是否可以在线性时间内解决这个问题呢？

解法二　空间换时间

思路

我们可以通过一个辅助的哈希表来降低时间复杂度，具体思路是：对数组进行遍历，遍历每一项时都判断target-nums[i]（其中i是当前数组项的索引值）是否在之前遍历中遇到过，如果是，则直接返回；如果不是，则将其放在哈希表中，然后继续遍历下一项。

代码

复杂度分析

●　时间复杂度：O(n)，其中n为数组长度。

●　空间复杂度：O(n)，其中n为数组长度。

这种方法能够在线性时间内完成，但是相应地使用了额外的n的空间。这在很多情况下是值得的，不但可以使程序运行得更快，代码也更简洁，这种算法对于这种需要返回索引的场景非常有效。比如题目要求返回的两个索引值按照在原数组中出现的先后顺序返回；又或者题目要求按照元素值的大小返回，我们也只需要拿出来比较一下，返回即可。总的来说，这种算法能应用的场景更多，代码更简洁，在没有对空间复杂度有特殊要求的场景下是首选。