Java 确定 Set S 中是否存在两个元素的总和恰好为 x - 正确解？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2171969/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?
提问by helpermethod
Taken from Introduction to Algorithms
摘自算法导论
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
描述一个 Θ(n lg n) 时间算法，给定一个由 n 个整数组成的集合 S 和另一个整数 x，确定 S 中是否存在两个元素的总和正好是 x。
This is my best solution implemented in Java so far:
到目前为止，这是我用 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;
}
Now my 1st question is: Is this a correct solution? From my understanding, mergeSort should perform the sort in O(n lg n), the loop should take O(n lg n) (n for the iteration multiplied by O(lg n) for the binary search, resulting in O(2n lg n), so it should be correct.
现在我的第一个问题是：这是一个正确的解决方案吗？根据我的理解，mergeSort 应该在 O(n lg n) 中执行排序，循环应该采用 O(n lg n)（n 为迭代乘以 O(lg n) 进行二分查找，结果为 O(2n lg) n)，所以它应该是正确的。
My 2nd question is: Are there any better solutions? Is sorting the array essential?
我的第二个问题是：有没有更好的解决方案？对数组进行排序是否必不可少？
采纳答案by codaddict
Your solution seems fine. Yes you need to sort because its a pre requisite for binary search. You can make a slight modification to your logic as follows:
您的解决方案看起来不错。是的，您需要排序，因为它是二分搜索的先决条件。您可以对您的逻辑稍作修改，如下所示：
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;
}
回答by Sean Owen
Your analysis is correct, and yes you must sort the array or else binary search does not work.
您的分析是正确的，是的，您必须对数组进行排序，否则二进制搜索不起作用。
回答by meriton
I do think I have spotted a minor bug in your implementation, but testing should uncover that one quickly.
我确实认为我在您的实现中发现了一个小错误，但测试应该很快发现这个错误。
The approach looks valid, and will reach the desired performance. You might simplify it by replacing the iterative binary search with a scan through the array, in effect replacing the binary search by a linear search that resumes where the previous linear search left off:
该方法看起来有效，并将达到所需的性能。您可以通过用对数组的扫描替换迭代二分搜索来简化它，实际上用线性搜索替换二分搜索，该线性搜索从前一个线性搜索停止的地方恢复：
int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
while (a[i] + a[j] > val) {
j--;
}
if (a[i] + a[j] == val) {
// heureka!
}
}
This step is O(n). (Proving that is left as an exercise for you.) Of course, the entire algorithm still takes O(n log n) for the merge sort.
这一步是 O(n)。（证明留给您作为练习。）当然，整个算法仍然需要 O(n log n) 进行归并排序。
回答by danben
This is correct; your algorithm will run in O(n lg n) time.
There is a better solution: your logic for calculating diff is incorrect. Regardless of whether
a[i]is greater than or less thanval, you still need diff to beval - a[i].
这是对的; 您的算法将在 O(n lg n) 时间内运行。
有一个更好的解决方案：您计算 diff 的逻辑不正确。不管
a[i]是大于还是小于val，你仍然需要 diffval - a[i]。
回答by Itay Maman
Here's an O(n) solution using a hash-set:
这是使用哈希集的 O(n) 解决方案：
public static boolean test(int[] a, int val) {
Set<Integer> set = new HashSet<Integer>();
// Look for val/2 in the array
int c = 0;
for(int n : a) {
if(n*2 == val)
++c
}
if(c >= 2)
return true; // Yes! - Found more than one
// Now look pairs not including val/2
set.addAll(Arrays.asList(a));
for (int n : a) {
if(n*2 == val)
continue;
if(set.contains(val - n))
return true;
}
return false;
}
回答by SyntaxT3rr0r
There's another very fast solution: Imagine you have to solve this problem in Java for about 1 billions integers. You know that in Java integers go from -2**31+1to +2**31.
还有另一个非常快速的解决方案：想象一下，您必须用 Java 解决大约 10 亿个整数的这个问题。您知道在 Java 中整数从-2**31+1到+2**31。
Create an array with 2**32billion bit (500 MB, trivial to do on today's hardware).
创建一个2**32十亿位的数组（500 MB，在今天的硬件上做起来很简单）。
Iterate over your set: if you have an integer, set corresponding bit to 1.
迭代你的集合：如果你有一个整数，将相应的位设置为 1。
O(n) so far.
O(n) 到目前为止。
Iterate again over your set: for each value, check if you have a bit set at "current val - x".
再次迭代您的集合：对于每个值，检查您是否在“当前 val - x”处设置了位。
If you have one, you return true.
如果有，则返回 true。
Granted, it needs 500 MB of memory.
当然，它需要 500 MB 的内存。
But this shall run around any other O(n log n) solution if you have, say, to solve that problem with 1 billion integers.
但是，如果您要使用 10 亿个整数解决该问题，那么这将围绕任何其他 O(n log n) 解决方案运行。
O(n).
在）。
回答by Neal Gafter
A simple solution is, after sorting, move pointers down from both ends of the array, looking for pairs that sum to x. If the sum is too high, decrement the right pointer. If too low, increment the left one. If the pointers cross, the answer is no.
一个简单的解决方案是，在排序后，将指针从数组的两端向下移动，寻找总和为 x 的对。如果总和太高，则递减右指针。如果太低，增加左边的一个。如果指针交叉，答案是否定的。
回答by sij
Here's is an alternate solution, by adding few more conditions into mergesort.
这是一个替代解决方案，通过在合并排序中添加更多条件。
public static void divide(int array[], int start, int end, int sum) {
if (array.length < 2 || (start >= end)) {
return;
}
int mid = (start + end) >> 1; //[p+r/2]
//divide
if (start < end) {
divide(array, start, mid, sum);
divide(array, mid + 1, end, sum);
checkSum(array, start, mid, end, sum);
}
}
private static void checkSum(int[] array, int str, int mid, int end, int sum) {
int lsize = mid - str + 1;
int rsize = end - mid;
int[] l = new int[lsize]; //init
int[] r = new int[rsize]; //init
//copy L
for (int i = str; i <= mid; ++i) {
l[i-str] = array[i];
}
//copy R
for (int j = mid + 1; j <= end; ++j) {
r[j - mid - 1] = array[j];
}
//SORT MERGE
int i = 0, j = 0, k=str;
while ((i < l.length) && (j < r.length) && (k <= end)) {
//sum-x-in-Set modification
if(sum == l[i] + r[j]){
System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + r[j]);
}
if (l[i] < r[j]) {
array[k++] = l[i++];
} else {
array[k++] = r[j++];
}
}
//left over
while (i < l.length && k <= end) {
array[k++] = l[i++];
//sum-x-in-Set modification
for(int x=i+1; x < l.length; ++x){
if(sum == l[i] + l[x]){
System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + l[x]);
}
}
}
while (j < r.length && k <= end) {
array[k++] = r[j++];
//sum-x-in-Set modification
for(int x=j+1; x < r.length; ++x){
if(sum == r[j] + r[x]){
System.out.println("THE SUM CAN BE OBTAINED with the values" + r[j] + " " + r[x]);
}
}
}
}
But the complexity of this algorithm is still not equal to THETA(nlogn)
但是这个算法的复杂度仍然不等于 THETA(nlogn)
