为了简单起见，数组中没有重复数字。

举例：

数组 A = [1, 5, 7, 2, 4, 6] 满足和为 10 的两个数字为 4 和 6。

解题思路一：

穷举，即任取两个数的组合，一共的可能性为 c(n, 2) = n!/((n-2)!2!) = n(n-1) / 2, 故其时间复杂度为 O(n*n)。

解题思路二：

只要在数组中能够寻找到 Sum - A[i] 的数即可。

  • 因为要查找，所以将原数组进行一次排序，这里使用堆排序，其时间复杂度为 O(n*logn)。
  • 有序数组，采用二分查找，其时间复杂度为 O(log2n) 。
  • 一次循环查找，所以总的时间复杂度为 O(n*log2n)。

解题思路三：

和思路二相似，只是不需要排序，并将步骤 2 中查找算法换成 hash 表， 那么查找的时间复杂度降为 O(1)，故总的时间复杂度为 O(n)，不过这样会带来额外的空间开销。

最近失眠越来越严重了，爬起来随便写了点东西。