有N个数的数组，找出这个数组中的两个数，使得这两个数的和最接近0
<div id="cnblogs_post_body">有N个数的数组，没有顺序。现在的问题是让你在数组中找出两个数，使得这两个数的和尽可能的接近0。想到的的方法是尝试所有数对<xi,xj>的组合，之后找出其中和的绝对值最小的数对即可。但是这样做的时间复杂度是O(N^2)，有没有更快一点的方法呢？
这里给出一个O(NlogN)时间复杂度的算法。
有一种比较直观的做法。
对数组排好序之后。如果数字全部是正数，那么取最小的两个数的和。如果数字全部是负数，则取最大的两个数字的和。如果数字有正有负。那么我们必须枚举每一个xi，之后用二分在数组中找小于等于-xi的最大值和大于等于-xi的最小值。能与xi构成和的绝对值最小的数字，肯定就是这两个数字中的某一个。所有的xi都枚举过之后，我们就可以找出和的绝对值最小值了。时间复杂度是O(NlogN)。
还有一种比较简便的做法，但是证明有些复杂。
1:对数组中的数进行从小到大排序。
2:设置两个游标，一个指向第一个数，另一个指向最后一个数，之后进行如下操作：把游标处的两个数相加取绝对值，与记录当前已经得到的最小绝对值比较，小则记录。之后对游标处的数的绝对值进行比较，移动指向数字绝对值较小的游标(如果是左面的游标指向的数字绝对值小，则向右移动，否则右面的游标向左移动)。循环此步骤，直至找到最小绝对值0或者游标相遇。
<div class="cnblogs_code">举个例子：原始序列：-2 3 4 -7 9 5排序后：-7 -2 3 4 5 9寻找过程：res = MAX_INF;-7 -2 3 4 5 9| | res = 2-7 -2 3 4 5 9| | res = 2-7 -2 3 4 5 9 | | res = 2-7 -2 3 4 5 9 | | res = 2-7 -2 3 4 5 9 | | res = 1-7 -2 3 4 5 9 | res = 1
页:
[1]