Find two values that add up to the sum I was working on a practice Java exam online:


  Write a function that, given a list and a target sum, returns
  zero-based indices of any two distinct elements whose sum is equal to
  the target sum. If there are no such elements, the function should
  return null.
       For example, findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) should return a single dimensional array with two elements and contain any of
  the following pairs of indices:

1 and 4 (3 + 9 = 12)
2 and 3 (5 + 7 = 12)
3 and 2 (7 + 5 = 12)
4 and 1 (9 + 3 = 12)



Here is my solution:

public class TwoSum {

    public static int[] findTwoSum(int[] list, int sum) {
        int[] twoSum = null;
        if(list != null){
            int listSize = list.length;
            int mod = listSize % 2;
            int half = listSize/2;
            int stop = mod &gt; 0 ? half+1 : half;
            if(listSize &gt;= 2){
                outer: for(int currentIndex=0; currentIndex&lt;listSize; currentIndex++){
                            if(currentIndex == stop){
                                break;
                            }
                            for(int otherIndex=0; otherIndex&lt;listSize; otherIndex++){
                                if(currentIndex &lt; otherIndex){
                                    int current = list[currentIndex];
                                    int other = list[otherIndex];
                                    int currentSum = current + other;
                                    if(currentSum == sum){
                                        twoSum = new int[]{currentIndex, otherIndex};
                                        break outer;
                                    }
                                }
                            }
                        }
            }
        }
        return twoSum;
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
        System.out.println(indices[0] + " " + indices[1]);
    }
}


My code passed all the unit tests, however, they have another check for a large list, and apparently my code runs too slow when the list size grows. Apart from me trying to decipher what their definition of too slow is, simply put, are there any optimizations I can make to have my code run faster? I tried to find the 'tipping point' in comparing numbers where I could stop checking, and I added that optimization, but apparently, that isn't good enough.
I would find this easier to read if the first thing in the method was 

        if (list == null || list.length &lt; 2) {
            return null;
        }


This gets rid of the unlikely cases off the bat and saves us having to indent the rest of the logic inside two if statements.  


            int listSize = list.length;
            int mod = listSize % 2;
            int half = listSize/2;
            int stop = mod &gt; 0 ? half+1 : half;



This could just be 

            int stop = (list.length + 1) / 2;


You never use mod or half elsewhere and can just replace listSize with list.length.  This will return the same results, as if the list has an odd size, adding one will give it an even size.  Then dividing by two will return the same result as half + 1, since half is rounded down.  If even, then adding one before dividing by two does nothing, as the odd number will be rounded down.  


                outer: for(int currentIndex=0; currentIndex&lt;listSize; currentIndex++){
                            if(currentIndex == stop){
                                break;
                            }



This could just be 

          for (int currentIndex = 0; currentIndex &lt; stop; currentIndex++) {


Although either way it returns an incorrect result for an input like 

new int[] { 1, 2, 9, 5, 7 }, 12


You do 


                                    int current = list[currentIndex];



inside the inner loop.  

Do it before the inner loop instead.  Then you can just do it once rather than once for each iteration of the inner loop.  On the bright side, the compiler probably compiled this out anyway.  


                                        twoSum = new int[]{currentIndex, otherIndex};
                                        break outer;



This could be just 

                            return new int[]{currentIndex, otherIndex};


Then you don't need the labeled loop.  And 


        return twoSum;



could be just 

        return null;


No need for the twoSum variable at all.  

Alternatives

This is an \$\mathcal{O}(n^2)\$ solution.  But this problem is solvable in linear time.  Consider 

public static int[] findTwoSum(int[] numbers, int target) {
    if (numbers == null) {
        return null;
    }

    Integer[] complements = new Integer[target];

    for (int i = 0; i &lt; numbers.length; i++) {
        if (complements[numbers[i]] != null) {
            return new int[]{complements[numbers[i]], i};
        }

        complements[target - numbers[i]] = i;
    }

    return null;
}


This works fine for modest sums where all the inputs are positive (like your example).  It will be much faster for large inputs.  

If those constraints don't work for you, try 

public static int[] findTwoSum(int[] numbers, int target) {
    if (numbers == null) {
        return null;
    }

    Map&lt;Long, Integer&gt; complements = new HashMap&lt;&gt;();

    for (int i = 0; i &lt; numbers.length; i++) {
        Integer complementIndex = complements.get((long)numbers[i]);
        if (complementIndex != null) {
            return new int[]{complementIndex, i};
        }

        // it's possible that for large targets and a negative input
        // that we might overflow the int type
        long complement = (long)target - numbers[i];
        complements.put(complement, i);
    }

    return null;
}


Now it doesn't matter if the target sum is large or some of the numbers are negative.  

Either version works by storing the locations of the complements for each value.  We only need to loop once and get/put are constant time operations for a HashMap.