java - O(n log(n)) 算法，检查 int[] 中的 2 个数字之和是否 = 给定数字

Suppose x is the sum we want to check, z is the set of elements in this array: The following algorithm solves the problem:

1. Sort the elements in S.
2. Form the set S’ = {z : z = x − y for some y ∈ S}.
3. Sort the elements in S'.
4. If any value in S appears more than once, remove all but one instance. Do the same for S’.
5. Merge the two sorted sets S and S’.
6. There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.

To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in S whose sum is exactly x if and only if the same value appears twice in the merged output. Suppose that some value w appears twice. Then w appeared once in S and once in S’. Because w appeared in S’, there exists some y ∈ S such that w = x − y, or x = w + y. Since w ∈ S, the elements w and y are in S and sum to x.

Conversely, suppose that there are values w, y ∈ S such that w + y = x. Then, since x − y = w, the value w appears in S’. Thus, w is in both S and S’, and so it will appear twice in the merged output.

Steps 1 and 3 require O(n log n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n log n).

``````class FindSum {

public static void main(String[] args) {
int[] arr = {6,1,2,3,7,12,10,10};
int targetSum = 20;

Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
int end = arr.length - 1;
if (FindSum.binarySearchSum(arr, targetSum, 0, end, 0, end)) {
System.out.println("Found!");
} else {
System.out.println("Not Found :(");
}
}

public static boolean binarySearchSum(int[] arr, int targetSum,
int from1, int end1,
int from2, int end2) {
// idea is to use 2 "pointers" (simulating 2 arrays) to (binary) search
// for target sum
int curr1 = from1 + (end1-from1)/2;
int curr2 = from2 + (end2-from2)/2;
System.out.print(String.format("Looking between %d to %d, %d to %d: %d, %d", from1, end1, from2, end2, curr1, curr2));
int currSum = arr[curr1] + arr[curr2];
System.out.println(". Sum = " + currSum);

if (currSum == targetSum) {
// base case
return true;
} else if (currSum > targetSum) {
// currSum more than targetSum
if (from2 != end2) {
// search in lower half of 2nd "array"
return FindSum.binarySearchSum(arr, targetSum, from1, end1, from2, curr2 - 1);
} else if (from1 != end2) {
// search in lower half of 1st "array" (resetting the start2, end2 args)
return FindSum.binarySearchSum(arr, targetSum, from1, curr1 - 1, 0, arr.length - 1);
} else {
// can't find
return false;
}
} else {
// currSum < targetSum
if (from2 != end2) {
// search in upper half of 2nd "array"
return FindSum.binarySearchSum(arr, targetSum, from1, end1, curr2 + 1, end2);
} else if (from1 != end2) {
// search in upper half of 1st "array" (resetting the start2, end2 args)
return FindSum.binarySearchSum(arr, targetSum, curr1 + 1, end1, 0, arr.length - 1);
} else {
// can't find
return false;
}
}
}

}
``````

``````int total = 9;
Integer[] S = {1, 4, 7, 2, 3, 4, 6};
Set<Integer> set = new HashSet<Integer>(Arrays.asList(S));
for (int i : set)
if (set.contains(total - i))
System.out.println(i + " + " + (total - i) + " = " + total);
``````

``````2 + 7 = 9
3 + 6 = 9
6 + 3 = 9
7 + 2 = 9
``````