【问题描述】无序数组中找出和为N的两个数，例如，nums = [1, 4, 3, 2, 6, 5]中找出和为target = 6的序列，答案：[(1, 5), (4, 2)]。

参考博客：

1、一个无序数组中两个数之和等于给定的值sum

2、Python算法题----在列表中找到和为s的两个数字

输入：

nums = [1, 4, 3, 2, 6, 5]

target = 6

输出 ：

[(1, 5), (4, 2)]

方法一：暴力——穷举法（O(N^2)）

       思想：嵌套循环，外层循环遍历全部列表，内层循环遍历当前元素位置之后的所有元素。内层循环中将两个数字相加，等于target，保存当前结果。需要注意的是同一个元素不能重复使用！

运行结果：

小结：这个思想确实简单，很容易想到，可能不具有挑战性！毕竟时间复杂度为O(N^2)，那有没有更好的方法呢？答案是肯定的，比如O(NlogN)与O(N)。

方法二：双指针——快速排序思想，O(NlogN)

        思想：来自于快速排序，在一个有序的数组（从小到大）中最左边一定是最小值，最右边是最大值。我们可将最小值与最大值相加与目标值进行比较，如果两数之和大于目标值，我们就让最大值小一点（读取第二个最大值），如果两数之和小于目标值，我们就让最小值大一点（读取第二个最小值），如果两数之和刚好等于目标值，保存最大值，最小值，并且让最大值小一点，最小值大一点。需要注意的是前提条件是数组必须有序！！！

        简化：对nums先排序，然后定义两个指针，一个low = 0指向数组头，一个high = len(nums) - 1指向数组的尾，看其和nums[low]+nums[high]是否== target；若==，则查找成功返回；若>sum，则尾指针high--；若= 2: low, high = 0, len1-1 while low < high: if nums[low] + nums[high] == target: res.append((nums[low], nums[high])) low += 1 high -= 1 elif nums[low] + nums[high] > target: high -= 1 else: low += 1 return res if __name__ == "__main__": nums = [int(i) for i in input().split()] target = int(input()) print(getRes_QuickSort(nums, target))

运行结果：

       细心的朋友这里会发现，诶，最后的输出结果顺序不对啊，因为我们是对排序后的数组进行查找的，如果想要返回原来的，还需进一步改进。

       需要注意的是，这里的排序算法选择的是时间复杂度为O(NlogN)的，加上查找所花时间O(N)，最终为O(NlogN)。肯定有人会想，那我为啥不选择时间复杂度为O(N)的排序算法（如：非比较排序的基数排序、计数排序或桶排序）先排序，再查找呢？这样结果就是O(N)了，效率岂不是更高，哎呀，你真的很聪明！！！但是接下面的方法，并不是这样做的，而是利用哈希表来完成！

方法三：哈希表思想求解，O(N)

        思想：给定一个数，根据hash表查找另一个数只需要O(1)的时间。但需要空间换时间，空间复杂度为O(n)；可以用hashMap实现，hashMap。遍历一遍数组，若次数没有存在hashMap中，则将其加入，次数为1；再遍历一遍数组，对每个值nums[i]，判断target - nums[i]是否在hashmap中【即对应的value是否==1】；若存在，则查找成功；否则继续遍历下一个。直到遍历完整个数组。

运行结果：

变式：给定一个无序数组，求

（1）三个数或四个数，甚至N个数之和等于target；

（2）两个数之差等于target；

这些都可以采取上面三种方法中的思想进行求解，但是，如果作为面试，后面两种才是面试官想要看到的解法！！！

练习一：剑指offer——和为S的两个数

输入描述：

        输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述：

        对应每个测试案例，输出两个数，小的先输出。

例如：

输入（假设无序）：

         1 4 3 2 6 5

         6

输出：[1,5]

输入：

          1 3 4 6 7 8

           45

输出：

           []

或者精简版本：