Finding pairs of numbers within A that add up to N I am working on an interview question from Amazon Software Interview:


  Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N


I have a working solution in Java:

static void allPairsAddToN(int[] array, int n) {
    for(int c=0;c&lt;array.length; c ++) {
        for(int j=c+1; j&lt;array.length; j++) {
            if(array[c] + array[j] == n)
                System.out.println("(" + array[c] +", " + array[j] +")" );
        }
    }
}


Is this the most efficient solution? To me, this is the brute force approach that runs in \$O(n^2)\$. But for this problem, wouldn't you have to try every possibility (unsorted)? Is there some trick where you don't?
If you had a sorted array of n numbers, then finding pairs that sum to N should take O(n) time.

Sorting should take O(n log n) time.

O(n log n + n) is O(n log n).  That's better than O(n2).  Therefore, you would be better off sorting the array first.