java - 在数组中查找具有重复项的和对，时间复杂度为 O(n)

Question

具有重复项的数组[4,4,1]。在 O(n) 中查找总和为 5 的对。 预期输出 (4,1) 和 (4,1)，计数为 2。

方法#1: 使用HashSet:

public static int twoSum(int[] numbers, int target) {
    HashSet<Integer> set = new HashSet<Integer>();
    int c = 0;
    for(int i:numbers){
      if(set.contains(target-i)){
        System.out.println(i+"-"+(target-i));
        c++;
      }
      set.add(i);
    }
     return c; 
    }

输出为1。

本文 link 中所述的方法 #2 :

private static final int MAX = 100000; 

    static int printpairs(int arr[],int sum)
    {
      int count = 0;
        boolean[] binmap = new boolean[MAX];
        for (int i=0; i<arr.length; ++i)
        {
            int temp = sum-arr[i];
            if (temp>=0 && binmap[temp])
            {
                count ++;
            }
            binmap[arr[i]] = true;
        }
      return count;
    }

输出1。

然而，O(nlog n) 解决方案是使用对数组进行排序:

 public static int findPairs(int [] a, int sum){

    Arrays.sort(a);
    int l = 0;
    int r = a.length -1;
    int count = 0;
    while(l<r){

      if((a[l] + a[r]) == sum){
         count ++;
        System.out.println(a[l] + " "+ a[r]);
        r--;
      }
      else if((a[l] + a[r])>sum ){
        r--; 
      }else{
        l++;
      }
    }
    return count;
  }

我们能在O(n)内得到解决方案吗？

Answer 1

您可以使用第二种方法 - 只需将 boolean 更改为 int:

public static void main(String[] args) {
    System.out.println(printPairs(new int[]{3, 3, 3, 3}, 6)); // 6
    System.out.println(printPairs(new int[]{4, 4, 1}, 5)); // 2
    System.out.println(printPairs(new int[]{1, 2, 3, 4, 5, 6}, 7)); // 3
    System.out.println(printPairs(new int[]{3, 3, 3, 3, 1, 1, 5, 5}, 6)); // 10
}

public static int printPairs(int arr[], int sum) {
    int count = 0;
    int[] quantity = new int[sum];
    for (int i = 0; i < arr.length; ++i) {
        int supplement = sum - arr[i];
        if (supplement >= 0) {
            count += quantity[supplement];
        }
        quantity[arr[i]]++; // You may need to check that arr[i] is in bounds
    }
    return count;
}