Find two numbers that add up to a given total, from a formatted string
Improved algorithm

You can significantly reduce the memory requirements of your algorithm by not creating any objects, including avoiding Maps, Sets, and String concatenations (the +s you use in print statements). You only need to use a constant amount of memory, comprised completely of primitives stored on the stack (avoiding garbage collection).

You can significantly reduce the time requirements of your algorithm by using a simple trick that allows you to scan the input list only once by moving toward the middle from the left and the right.

public final class SumPairs {
    public static final void printSumPairs(final String input) {
        final int inputLength = input.length();

        // On the left, move to the very first number.
        int leftStartIndex = 0;
        int leftEndIndex   = input.indexOf(',', 1);
        int leftNumber     = parseIntFromSubstring(input, leftStartIndex, leftEndIndex);

        // On the right, move to the very last number.
        int rightEndIndex   = input.lastIndexOf(';', inputLength - 2);
        int rightStartIndex = input.lastIndexOf(',', rightEndIndex - 2) + 1;
        int rightNumber     = parseIntFromSubstring(input, rightStartIndex, rightEndIndex);

        // Figure out the desired sum.
        final int desiredSum = parseIntFromSubstring(input, rightEndIndex + 1, inputLength);

        boolean noOutputYet = true;

        while (leftStartIndex &lt; rightStartIndex) {
            final int currentSum = leftNumber + rightNumber;

            if (currentSum &gt; desiredSum) {
                // On the right, move to the previous distinct number.
                int oldRightNumber;
                do {
                    oldRightNumber = rightNumber;

                    rightEndIndex   = rightStartIndex - 1;
                    rightStartIndex = input.lastIndexOf(',', rightEndIndex - 2) + 1;
                    rightNumber     = parseIntFromSubstring(input, rightStartIndex, rightEndIndex);
                } while ((rightNumber == oldRightNumber) &amp;&amp; (leftStartIndex &lt; rightStartIndex));
            }
            else { 
                if (currentSum == desiredSum) {
                    if (noOutputYet) noOutputYet = false;
                    else System.out.print(';');

                    System.out.print(leftNumber);
                    System.out.print(',');
                    System.out.print(rightNumber);
                }

                // On the left, move to the next distinct number.
                int oldLeftNumber;
                do {
                    oldLeftNumber = leftNumber;

                    leftStartIndex = leftEndIndex + 1;
                    leftEndIndex   = input.indexOf(',', leftStartIndex + 1);
                    leftNumber     = parseIntFromSubstring(input, leftStartIndex, leftEndIndex);
                } while ((leftNumber == oldLeftNumber) &amp;&amp; (leftStartIndex &lt; rightStartIndex));
            }
        }

        if (noOutputYet) System.out.print("NULL");
        System.out.println();
    }

    // Java 7 and later's String#substring creates a new char[] array just about every time it's used.
    // Since Integer#parseInt requires a full String, we'd have to let String#substring create a lot of char[]s if we used Integer#parseInt.
    // We'd like to avoid that to reduce memory requirements and to eliminate garbage collection.

    // WARNING: This method doesn't actually check whether there is a valid number.
    //          That's your job!
    private static final int parseIntFromSubstring(final String str, int start, final int end) {
        int result = 0;
        final boolean negative = str.charAt(start) == '-';
        if (negative) start++;

        for (; start &lt; end; start++)
            result = 10*result + str.charAt(start) - '0';

        if (negative) return -result;
        else return result;
    }

    public static final void main(String[] args) {
        printSumPairs("1,2,3,4,5,6;6");
    }
}




Critiques

Problem statement


The part about outputting "NULL" should be in the section about output, not the section about input.
The characters in the input are not fully specified. Will there be spaces or other characters to ignore mixed in? Can numbers have a decimal point? Can numbers be negative? Are newlines separators for separate problems to solve?
The CodeEval challenge says not to output duplicate pairs. For example "3,3,3,3;6" should output "3,3", not "3,3;3,3;3,3;...".


Your solution


The problem statement says to read lines from a file, but your algorithm doesn't do that.
You don't need to sort the array of ints. The problem statement says they'll already be sorted.


Time complexity

Your code shouldn't be regarded as \$O(3n)\$ for a few reasons:


Big O notation ignores constant multiples like 3. It should be \$O(n)\$, not \$O(3n)\$.
You use Arrays#sort when you don't need to. While it uses a nicer version of quicksort than normal, it still has a \$O(n^2)\$ worst case time complexity.
If you're limiting your algorithm to a list of unique 32-bit integers, there's only so many of those available to put in your input list. This means that there will be an input that takes the longest amount of time to produce an answer. This means that you have a constant upper bound on the time needed, which makes your algorithm (including your 'naive' one) \$O(1)\$.

If you're not limiting your algorithm to a list of unique 32-bit integers, then you should realize that it takes a lot longer to add together two integers with billions of digits than it does to add 1 and 2. The time complexity of addition is \$O(m)\$, where \$m\$ is the number of digits in the largest number in the input list. This means your complexity will be \$O(mn)\$.