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

Question

我应该创建一个 O(n log(n)) 算法来检查 int[] 中的两个数字之和是否 == 给定数字。

例如。给定 [1,4,7,2,3,4] 总和为 8 (1+7) 但不是 20

给出的答案建议使用二元排序或归并排序，但他们只是给出了归并排序算法，而没有逻辑处理这一特定要求。然后另一个答案是:

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).

但我真的不明白他们的意思。在第二步中，x 和 y 是什么？

但是我下面是自己创建的，不知道是不是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;
      }
    }
  }

}

Answer 1

类似于@user384706，但是您可以在 O(n) 中完成此操作。

他们说的是: S=[1,4,7,2,3,4]

将这些添加到一个HashSet中，最好是TIntHashSet(但时间复杂度是一样的)

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