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<array.length; c ++) {
        for(int j=c+1; j<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.

StackExchange Code Review Q#82965, answer score: 4