Find integer pairs in an array which adds to a given sum I came up with the following solution. 


Is there a better way to solve this problem than the proposed? 
Also I used LinkedList to convey the result back to the API caller. Is there a better data structure to use? 
I tried using a 2 dimensional array to store the pairs, but int creation requires a size, which we are not aware of until we evaluate the array. So I had to use a LinkedList where the size can be dynamic.




public class FindPairsInAnArrayAddingToASum {

    private static class ResultPair{
        ResultPair prev;
        ResultPair next;
        int a;
        int b;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] items = new int[]{1,2,3,4,5,5,6,7};
        System.out.println("Pairs: ");
        ResultPair currentNode = getPairsAddingToSum(items, 10);
        while(currentNode != null){
            System.out.println("--&gt; "+currentNode.a+", "+currentNode.b);
            currentNode = currentNode.next;
        }
    }

    public static ResultPair getPairsAddingToSum(int[] items, int prescribedSum){
        ResultPair headNode = null;
        ResultPair currentNode = null;

        //Sort the array
        Arrays.sort(items);

        //Introduce left and right pointers
        int left = 0;
        int right = items.length-1;

        //Navigate from both directions
        while(left &lt; right){
            if(items[left] + items[right] == prescribedSum){

                currentNode = addThePair(items[left], items[right], currentNode);

                //Save the head - Only the first time a node is created
                if(headNode == null)
                    headNode = currentNode;

                //Increment left and decrement right
                left++;
                right--;

            }else if(items[left] + items[right] &lt; prescribedSum){
                left++;
            }else{
                right--;
            }
        }

        return headNode;
    }

    public static ResultPair addThePair(int a, int b, ResultPair currentNode){
        ResultPair newNode = new ResultPair();
        newNode.a = a;
        newNode.b = b;
        if(currentNode != null){
            currentNode.next = newNode;
            newNode.prev = currentNode;
        }
        return newNode;
    }

}
I like your approach with the two-pointer-array. As for the performance: The other answers here use the Big O notation as a basis for comparing the speed of different algorithms, hinting that using a HashMap or a HashSet might be faster than your approach. But this is misleading, since the Big O notation says nothing about the speed of different algorithms compared to each other, but only about how much slower an algorithm will be when \$n\$ increases. For example, you might have an \$O(n)\$ algorithm that takes \$n\$ hours to complete, and an \$O(n^{2})\$ algorithm that takes \$n^{2}\$ milliseconds to complete, and the second algorithm will be faster for all \$n &lt; 3600000\$. Of course, this is an extreme example, I just wanted to make a principle clear.

As for this case, I tried to compare your algorithm with the algorithm suggested by zenwraight. Here is my implementation of that algorithm:

public class FindPairsInAnArrayAddingToASum {
    public static class IntegerPair {
        public final int number1;
        public final int number2;

        public IntegerPair(int number1, int number2) {
            this.number1 = number1;
            this.number2 = number2;
        }
    }

    public static List&lt;IntegerPair&gt; findNumberPairs(int[] items, int prescribedSum) {
        Map&lt;Integer, Integer&gt; frequencies = new HashMap&lt;&gt;();
        for (int item : items) {
            Integer previousFrequency = frequencies.get(item);
            frequencies.put(
                    item,
                    previousFrequency != null
                    ? previousFrequency + 1
                    : 1);
        }

        List&lt;IntegerPair&gt; result = new LinkedList&lt;&gt;();
        for (int item : frequencies.keySet()) {
            int complement = prescribedSum - item;
            Integer complementFrequency = frequencies.get(complement);
            if (complementFrequency != null
                    &amp;&amp; (item != complement || complementFrequency &gt; 1)) {
                result.add(new IntegerPair(item, complement));
            }
        }

        return result;
    }
}


First, I benchmarked 10 test cases where every array contains 10,000 random integers, with a different random prescribed sum for every array. Here are the results:

Double pointer array: 0.022 seconds
Hash map: 0.066 seconds

Double pointer array: 0.012 seconds
Hash map: 0.036 seconds

Double pointer array: 0.017 seconds
Hash map: 0.021 seconds

Double pointer array: 0.003 seconds
Hash map: 0.071 seconds

Double pointer array: 0.006 seconds
Hash map: 0.013 seconds

Double pointer array: 0.006 seconds
Hash map: 0.009 seconds

Double pointer array: 0.008 seconds
Hash map: 0.01 seconds

Double pointer array: 0.003 seconds
Hash map: 0.009 seconds

Double pointer array: 0.003 seconds
Hash map: 0.007 seconds

Double pointer array: 0.002 seconds
Hash map: 0.008 seconds


So your code performed slightly better in all test cases listed here (although there also were some 10,000-size array test cases in other benchmark runs where the HashMap performed slightly better). Next, 10 test cases, same as above, but now the arrays contain 100,000 integers:

Double pointer array: 0.064 seconds
Hash map: 0.346 seconds

Double pointer array: 0.068 seconds
Hash map: 0.381 seconds

Double pointer array: 0.03 seconds
Hash map: 0.068 seconds

Double pointer array: 0.032 seconds
Hash map: 0.12 seconds

Double pointer array: 0.032 seconds
Hash map: 0.17 seconds

Double pointer array: 0.037 seconds
Hash map: 0.073 seconds

Double pointer array: 0.014 seconds
Hash map: 0.12 seconds

Double pointer array: 0.013 seconds
Hash map: 0.054 seconds

Double pointer array: 0.016 seconds
Hash map: 0.059 seconds

Double pointer array: 0.014 seconds
Hash map: 0.066 seconds


Your code still wins. The differences are even more significant in some cases than when the arrays only contained 10,000 integers. Next, increase the array size to 1,000,000 integers:

Double pointer array: 0.495 seconds
Hash map: 2.356 seconds

Double pointer array: 0.336 seconds
Hash map: 3.916 seconds

Double pointer array: 0.279 seconds
Hash map: 0.651 seconds

Double pointer array: 0.164 seconds
Hash map: 0.713 seconds

Double pointer array: 0.162 seconds
Hash map: 0.885 seconds

Double pointer array: 0.31 seconds
Hash map: 0.868 seconds

Double pointer array: 0.164 seconds
Hash map: 0.795 seconds

Double pointer array: 0.165 seconds
Hash map: 0.919 seconds

Double pointer array: 0.323 seconds
Hash map: 0.71 seconds

Double pointer array: 0.164 seconds
Hash map: 0.697 seconds


Your double pointer array beats the hash map again. Finally, increase the array size to 5,000,000 (the program ran out of memory when I tried to run it with 10,000,000-size arrays, probably because I generated all 10 test cases in advance instead of only generating one for each benchmark).

Double pointer array: 1.625 seconds
Hash map: 14.116 seconds

Double pointer array: 0.927 seconds
Hash map: 12.554 seconds

Double pointer array: 0.914 seconds
Hash map: 11.51 seconds

Double pointer array: 0.924 seconds
Hash map: 10.654 seconds

Double pointer array: 1.013 seconds
Hash map: 15.335 seconds

Double pointer array: 1.039 seconds
Hash map: 10.512 seconds

Double pointer array: 0.9 seconds
Hash map: 11.928 seconds

Double pointer array: 0.954 seconds
Hash map: 10.16 seconds

Double pointer array: 0.916 seconds
Hash map: 12.326 seconds

Double pointer array: 0.899 seconds
Hash map: 9.881 seconds


I don't know why the HashMap algorithm takes so long here. It could have to do with the need to increase the capacity of the HashMap multiple times, but experimenting with different values for the initial capacity didn't make much of a difference. But anyway, I think this makes it clear that you shouldn't rely on the Big O notation when comparing the speed of different algorithms to each other.

However, apart from the performance, your public method getPairsAddingToSum(int[], int) returns a ResultPair, which is a private class, so whoever calls your method won't be able to do anything with the returned value. But regardless of that, I don't understand why, in your code, you invent something that already exists, namely a linked list. Why don't you just use java.util.LinkedList?

In any case, you also asked whether there would be a better data structure than a linked list to return the found pairs. I think there is, namely a Set. After all, the array might contain duplicates, so it might also contain duplicate valid pairs. Of course, in order to take advantage of a Set, you would have to implement hashCode() and equals(Object) in your ResultPair class (which would then only contain the two integers and no nodes). Seeing as, in your algorithm, the first number in a pair will always be less than or equal to the second number, it would suffice for ResultPair.equals(Object) to compare a and b from both ResultPairs to each other without sorting them first, thereby considering to ResultPairs with the same numbers but in a different order unequal, but this depends on how you want to use the class ResultPair further (in case you do want to use it outside the context of this algorithm). Note that, if you use a Set, the algorithm will naturally take longer than if you use a List, because removing duplicates is an additional task that was not carried out in your original code.

Edit:

Actually, there's a much simpler and more efficient approach for avoiding duplicate number pairs than using a Set: When adjusting the array counters for the next while loop, you could simply in-/decrement them until the integer they point to is different from the integer they previously pointed to, instead of in-/decrementing them only once.