给定两个相同大小的数组，找到两个数组中的几个元素，它们与最小的绝对值进行求和

Question

昨天我接到了这个问题的任务，从那时起我就试图找到一个有效的解决方案。
解决方案的细节是：给定两个数组a [n]，b [n]，找到一个对（a [i]，b [j]），以便abs（a [i] + b [j]）尽可能小。这两个数组由整数元素组成，不超过10亿，这里n至多为10000.
我知道一个由两个for循环组成的解决方案是不实用的，因为数组的大小小于或等于10000.
I我正在考虑一种解决方案，我将以某种方式对这些元素进行排序，这是我尚未发现的，因此我们可以很容易地找出绝对值最小的和，因为我的课正在学习排序算法。
你能帮我弄清楚这里的方式吗？
PS：对不起，我无法在这里输入数学符号。

Answer 1

我有一个Python代码，在O(nlogn + mlogm) + O(m+n) = O(nlogn + mlogm)时间，其中n是第一阵列的长度和m是所述第二阵列的长度解决该问题。下面是代码：

arr1.sort() 
arr2.sort(reverse = True) 
n = len(arr1) 
m = len(arr2) 
print arr1 
print arr2 
minim = abs(arr1[0] + arr2[0]) 

i = 0 
j = 0 

while i<n and j<m: 
    minimum = abs(arr1[i] + arr2[j]) 
    minim = min(minim,minimum) 
    if arr1[i]>0 and arr2[j]>0: 
     j += 1 
    elif arr1[i]<=0 and arr2[j]<=0: 
     i += 1 
    elif arr1[i]>0 and arr2[j]<=0: 
     if abs(arr1[i]) > abs(arr2[j]): 
      j += 1 
     else: 
      i += 1 
    elif arr1[i]<=0 and arr2[j]>0: 
     if abs(arr1[i]) > abs(arr2[j]): 
      i += 1 
     else: 
      j += 1 

print minim 

实施例：

arr1[] = [-23, -10, 30, 44, 45]

arr2[] = [61, 55, 32, 22, -55]

答案：1

Answer 2

您可以否定其中一个列表并将其与其他列表一起排序。在这个新的列表中，您可以查找两个连续的最小距离的条目，并且这两个条目是每个原始列表中的一个条目。

如果a[i], i=0,1,...,n是第一个，而b[j], j=0,1,...,n是第二个，那么min(|a[k]+b[l]|)=min(|a[k]-(-b[l])|)。因此，对于某些k,l，我们可以将a[k]和b[l]的总和最小化，而对于某些k,l，我们可以最小化a[k]和-b[l]之间的差异。所以我们寻找一对a[k],-b[l]尽可能接近。这样的一对必须在从对i,j=0,1,...,n进行排序a[i], -b[j]获得的列表中连续成为长度为2n的单个列表c[t]。

排序c是O（n日志n），运行通过c是O（n），所以运行时间是由排序占主导地位。