取自算法导论
描述一个Θ（n lg n）时间算法，该算法在给定n个整数S和另一个整数x的集合S的情况下，确定S中是否存在两个元素的总和恰好是x。
到目前为止，这是我用Java实现的最佳解决方案：
public static boolean test(int[] a, int val) { mergeSort(a); for (int i = 0; i < a.length - 1; ++i) { int diff = (val >= a[i]) ? val - a[i] : a[i] - val; if (Arrays.binarySearch(a, i, a.length, diff) >= 0) { return true; } } return false; }
现在我的第一个问题是：这是正确的解决方案吗？根据我的理解，mergeSort应该在O（n lg n）中执行排序，循环应该使用O（n lg n）（n用于迭代乘以O（lg n）进行二进制搜索，结果为O（2n lg n），所以应该是正确的。
我的第二个问题是：是否有更好的解决方案？对数组进行排序是否必不可少？
您的解决方案似乎很好。是的，您需要排序，因为它是二进制搜索的先决条件。您可以对逻辑进行如下修改：
public static boolean test(int[] a, int val) { Arrays.sort(a); int i = 0; // index of first element. int j = a.length - 1; // index of last element. while(i<j) { // check if the sum of elements at index i and j equals val, if yes we are done. if(a[i]+a[j] == val) return true; // else if sum if more than val, decrease the sum. else if(a[i]+a[j] > val) j--; // else if sum is less than val, increase the sum. else i++; } // failed to find any such pair..return false. return false; }
