# Finding array indices that add up to another number

I'm writing a method that takes (1) an array of ints and (2) an int. The purpose of the method is to find the indices of the two numbers in the array that add up to the value passed in as the second parameter to the method (sum) and return those values in an int[]. Exactly two numbers in the passed in array will add up to "sum", so as soon as they are identified the method should finish. I have come up with two solutions so far, but both seem ugly to me:

//this method is bad because it has multiple returns
private int[] findIndexes(int[] intAr, int sum) {
for (int i = 0; i < intAr.length; ++i) {
for (int k = i + 1; k < intAr.length; ++k) {
if(intAr[i] + intAr[k] == sum) {
return new int[] {i + 1, k + 1};
}
}
}
//should never reach here
return null;
}
//this method is bad because it uses "break" outside of a switch statement
private int[] findIndexes(int[] intAr, int sum) {
int[] indexAr = new int[2];
outer:
for (int i = 0; i < intAr.length; ++i) {
for (int k = i + 1; k < intAr.length; ++k) {
if(intAr[i] + intAr[k] == sum) {
indexAr[0] = i + 1;
indexAr[1] = k + 1;
break outer;
}
}
}
return indexAr;
}


Is there a better way to write this method that does not violate the coding standards mentioned above?

The coding standards I was looking at are located here.

• Who told you they're bad? I believe it's a matter of opinion. – Jon Martin Aug 2 '11 at 19:49
• I see nothing wrong with your first method, nor the second, but I prefer the first. – Hovercraft Full Of Eels Aug 2 '11 at 19:53
• +1 for @Jon. Both of those "rules" are made to be broken. In either case, there's a third solution in which you use a boolean flag or two and check it in the loop condition (or equivalently inside the loop) to see whether a solution has been found or not: and it's far uglier than either of these. Personally, I like the first one, which is very clear and easy to follow. – Ernest Friedman-Hill Aug 2 '11 at 19:54
• You're already ignoring 1.1 - Braces in the standards you linked to. Why stick to the others? – Vlad Aug 2 '11 at 20:06
• Is there a reason you are checking the sum of the contents at i and k in the array, but returning an array populated with i + 1 and k + 1 values (not contents)? If your code does what it's stated to, you are assuming that 'x[n] == n + 1' - not something I would bet on in the wild (non-contiguous arrays, starting values not at 1, etc). I would also start k at i, not i + 1, in case the only way to match the sum is to double the number (and no duplicates in the array). Other than that, I like the first solution. – Clockwork-Muse Aug 2 '11 at 20:13

There's nothing wrong with a break statement used outside a switch statement. (2nd example)

If a professor or some other authority figure is enforcing that rule, that's a pain, but the code is perfectly fine. There's even a similar example in the Java Tutorials on Branching

As the majority already pointed out, your method is fine concerning the coding standards. However it has an asymptotic complexity of O(n²). For very long arrays you may consider a more performant approach having O(n * log n) [...I think]. The code is very easy to understand: Sort the array and search from both ends. The only difficulty is that you need to keep track of the indexes as well, which requires to copy the whole array.

private int[] findIndexes(int[] intAr, int sum) {
int[][] data = new int[intAr.length][2];
for(int i = 0; i < intAr.length; i++) {
data[i] = new int[]{intAr[i], i + 1};
}
java.util.Arrays.sort(data, new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int lower = 0;
int upper = data.length-1;
while(lower < upper) {
int s = data[lower][0] + data[upper][0];
if(s == sum) {
return new int[]{data[lower][1], data[upper][1]};
} else if (s < sum) {
lower++;
} else {
upper--;
}
}
return null;
}


Even if this solution isn't appropriate in your setting, it's useful to know this "search from both ends" technique. Obviously this approach would be much simpler if you can assume an already sorted array.

There is nothing wrong with having multiple return statements especially to break out of nested ifs.

Your first method seems perfectly fine to me. Having multiple returns in the same method is not necessarily bad -- how else would one implement Ackermann function? :). Your usage of the break in the second method, however, is not very common, and can thus be confusing, but it's also perfectly valid to use a break outside of a switch statement.