chris - 1 year ago 106
Java Question

# Find a sum pair in array with duplicates in O(n)

Array with duplicates

`[4,4,1]`
. Find pairs with sum
`5`
in
`O(n)`
.
Expected output
`(4,1)`
and
`(4,1)`
and count is
`2`
.

Approach#1:
Using
`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++;
}
}
return c;
}
``````

Output is
`1`
.

Approach #2 as stated in this link:

``````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;
}
``````

Output
`1`
.

However the
`O(nlog n)`
solution is using sorting the array:

`````` 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;
}
``````

Can we get the solution in
`O(n)`
?

You can use your second approach - just change `boolean` to `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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download