algorithm - 数组中两个整数之和等于 K

Question

我读了 Find two elements in an array that sum to k和How can I find two elements in an array that sum to k as they are related。

我知道一个 O(n) 解决方案，但我看到一个 O(n logn) 也存在：-

p=0,q=n-1;
while(p<q)
{
  if(a[p]+a[q]==k)
  {
      cout<<a[p]<<"\t"<<a[q];
      p++;
      q--;
   }
   else if(a[p]+a[q]>k)
      q--;
   else 
      p++;
}

这需要首先对数组进行排序。但是由于 p 和 q 的值取决于数组中的元素，我们如何断言这个算法的复杂度是 O(n Log n)？

Answer 1

有效排序算法的复杂度为O(n log n)。

无论p和以何种方式q变化，while循环都会遍历数组中的所有元素一次，因此它的复杂度是O(n).

将两者相加：O(n log n) + O(n) = O(n log n + n) = O(n log n)，因为 n 远小于n log n， whenn是一个大数。

Answer 2

如果您有O(n)解决方案，则无需担心自己，O(n log n)因为那样会更糟，除非该O(n)解决方案存在其他问题，例如巨大的空间复杂性，例如O(n^(n^(n^n))):-)

在任何情况下，您展示的算法也是O(n)因为您在每次迭代中增加低索引或减少高索引。

我怀疑O(n log n)您提到的首先包括初始类型的未排序数据，因为这是排序的典型时间复杂度。

Answer 3

在蟒蛇

arr = [1, 2, 4, 6, 10]
diff_hash = {}
expected_sum = 3
for i in arr:
    if diff_hash.has_key(i):
        print i, diff_hash[i]
    key = expected_sum - i
    diff_hash[key] = i

算法：

Input: expected_sum

diff_hash = hashtable_datastructure
for(i=0, i<len(arr), i++)
{ 
   if(diff_hash(arr[i])) 
   { 
      return arr[i] , diff_hash(arr[i])
   } 
   key = expected_sum - arr[i] 
   diff_hash(key) = arr[i] 
 }