algorithm - 在未排序的数组中找到一对数字，其总和最接近任意目标

Question

<分区>

Answer 1

第一步:对数组进行非降序排序。复杂度:O( n lg n )

第二步:从两端向内扫描。复杂度:O(n)

在排序数组 A 上，让 l 指向最左边(即最小)元素，r 指向右边-大多数(即最大)元素。

 while true:
   curSum = A[ l ] + A[ r ]
   diff = currSum - target
   if( diff > 0 ):
      r = r - 1
   else:
      l = l + 1

如果 diff == 0，那么您就得到了 2Sum 的完美匹配。

否则，在 diff 中寻找符号的变化，即从正向负向或从负向正向的转变。每当转换发生时，无论是在更改之前还是之后，currSum 都最接近 target。

整体复杂度:O( n log n ) 因为第 1 步。