在给定数组中，找出最先满足两个数的和等于给定数，输出这两个元素的下表

leetcode上的一道题目，虽然不难，但是考察了数据结构中很多的知识

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

1） 找到 两个数的和=target即可

穷举法，列出双层循环，从第一个开始，找到比target小的数，从这个数之后找两个数和=target的数，这样做的所循环次数为N+(N-1)+(N-2)+...+1 = 1/2(N*(N+1)),即复杂度为O(n²)，提交过去发现不对，超时，看来O(n²)复杂度太高了

 2）找到 满足 target-numbers[i]的数

这种即查找，常见的查找算法即直接查找O(n)和折半查找O(log₂n),对于一个无需数组的查找，对每个number[i]，都要查看target-number[i]在不在数组中,复杂度为O(n²)，折半需要先排序才能进行，用一种快速的排序算法( 堆排序，快速排序，O(log₂n))

快速排序：快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

_{对于快速排序，其空间复杂度为O（logn),最坏情况下，空间复杂度为O(n)，可以用pivot算法来将其降低到O（logn)(即对基本有序的数列进行随机选取一个基准点，不然每次都是左边或者右边序列为空)}

在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlog₂n)

尽管快速排序的最坏时间为O(n²)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

另外附上一张排序的图：

回到上一话题，即，先排序，在进行选择，排序算法复杂度为 O(nlog₂n),但幸好 只需一次，排序好之后，便可以进行O(nlog₂n)的查找，最后还是O(nlog₂n)

还有一种办法是构建一个哈希，哈希表建立表的时间复杂度为O(n)，查找的复杂度为O(1),但需要O(n)的空间复杂度，所以这是一种空间换时间的办法，有时候会很有效，最后哈希加折半的办法，使得复杂度变为O(n)+O(log₂n)即O(n)的时间+O(n)的空间

3）找到numbers中两两数之和

对一个数组中的数两两求和，其复杂度无疑是O(n*n)，但换一种思路，先排序，对排序好的数组分别建立两个指针指向队头队尾，target大了，则j前移，小了则i后移，直到找到sum记下两个下标i和j 

扩展问题

1、如果把这个问题中的“两个数字”改成“三个数字”或“任意个数字”时，你的解是什么呢？
三个数字：首先还是先对数组进行排序，然后从i=0到n-1进行遍历，遍历arr[i]时，在调用上面的函数getSumNum(arr , Sum-arr[i])即可。
任意m个数字的想法：
首先还是先对数组进行排序，然后从i=0到n-1个元素遍历，遍历arr[i]时，在剩下的n-1个元素中调用getSumNum(arr,Sum-arr[i])，此时为求m-1个元素和为Sum-arr[i]；接下来，同样的方法,从j=0到n-2个元素遍历，遍历arr[j]时在arr上递归调用getSumNum(arr,Sum-arr[i]-arr[j])，此时为求m-2个元素和为Sum-arr[i]-arr[j]；依次递归，直到为求2个元素和为Sum-?-?-?...时为止。
不论是求3个数字还好是m个数字，总是能比较穷举法少一个数量级n，比先排序然后二分查找求Sum-arr[i]也要快。