如何为两个未排序的数组代码编写此代码？

Question

二进制搜索的想法在排序数组的情况下完美地工作。我们可以对A[]进行排序，对于每个值A[i]，搜索数组中是否存在另一个值K-A[i]。二进制搜索在O（logn）中执行搜索，这可以帮助我们提高时间复杂度。

解决方案步骤

对数组A[]按递增顺序排序对于每个元素A[i]，使用二分查找K-A[i]。如果数组A中存在值K-A[i]，则返回true。如果在整个数组中没有找到这样的对，则返回false。

伪代码"'

int find_sumPair (A[], n, K)
     {
       Sort ( A, n)
       for( i = 0 to n-1 )
       { 
          x = binarySearch ( A, 0, n-1, K-A[i] )
          if ( x ) 
          return 1
       }
     return -1
     }

'''

这个伪代码只针对一个数组，如果我想检查两个未排序的数组中的对，以及伪代码的复杂度时间应该是O（nlogn）？？

Answer 1

上述方法在O（nlogn）时间内解决了这个问题。您可以在：O（nlogn）时间内对一个数组进行排序，然后您可以迭代另一个数组并对排序后的数组执行二进制搜索，以找到K-A[i]，即O（logn）时间，因此总时间变为O（nlogn）。所以TC将是O（nlogn）O（nlogn）=O（nlogn）。

您可以通过使用O（n）空间，使用hashmap在O（n）时间内解决这个问题。

#Pusedo code
arr1 = [...]
arr2 = [...]
K = some_value
hashmap = {k: True for k in arr1}

for each_element in arr2:
    if K-each_element in hashmap:
        return "sum found of element [each_element, K-each_element]"
return "no such sum present"