Home

小鱼驿站

06 Jul 2017

如何快速从一数组中找出两个数,使其和为一特定数字

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

举例:

数组 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),不过这样会带来额外的空间开销。

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

Til next time,
small_fish__ at 22:02

scribble