O(n log(n))算法,检查int []中给定数字的2个数的和

Question

我应该创建一个O(n log(n))算法,检查int [] ==给定数字中是否有2个数字的总和.

例如.鉴于[1,4,7,2,3,4]将有8(1 + 7)而不是20

给出的答案建议使用二进制排序或合并排序,但他们只给出了合并排序算法,而没有逻辑处理这个特殊要求.然后另一个答案是:

假设x是我们要检查的总和,z是此数组中的元素集:以下算法解决了以下问题:

1. 在S中排序元素
2. 形成集合S'= {z:z = x-y表示某些y∈S}.
3. 对S'中的元素进行排序.
4. 如果S中的任何值出现多次,则删除除一个实例外的所有值.为S'做同样的事情.
5. 合并两个有序集S和S'.
6. S中存在两个元素,当且仅当相同的值出现在合并输出的连续位置时,其总和才是x.

为了证明步骤4中的声明的合理性,首先观察如果在合并输出中出现两次任何值,它必须出现在连续的位置.因此,我们可以在步骤5中重述该条件,因为在S中存在两个元素,当且仅当相同的值在合并输出中出现两次时,其总和恰好为x.假设某个值w出现两次.然后在S中出现一次,在S'出现一次.因为w出现在S'中,所以存在一些y∈S,使得w = x-y,或x = w + y.由于w∈S,元素w和y在S中并且与x相加.

相反,假设存在值w,y∈S使得w + y = x.然后,由于x-y = w,值w出现在S'中.因此,w在S和S'中,因此它将在合并输出中出现两次.

步骤1和3需要O(n log n)步骤.步骤2,4,5和6需要O(n)步骤.因此总运行时间为O(n log n).

但我真的不是他们的意思.在第2步中,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

他们的说法如下：
S=[1,4,7,2,3,4]

使用您得到的归并排序对 S 进行排序Ss=[1,2,3,4,7]。成本是O(nlogn)- 只需检查 wiki 即可。

然后你有x=8
所以你S'=[7,6,5,4,1]通过减去x中的元素来形成S。在 Remove duplicates requires 中使用合并
排序S'进行排序。 O(nlogn)
O(n)

然后合并Ss和S'。
您检查 中连续位置的重复项O(n)。
总计为：
O(nlogn)+O(nlogn)+O(n)+O(n)+O(n) = O(nlogn)

Answer 2

与@ user384706类似,但您可以使用in来执行此操作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