Sum of two elements (2sum)

Given an array of integers and an integer target, return indices of the two numbers such that they add up to the target.

Photo: Two zebras
“Photo by Geran de Klerk on Unsplash

Given an array of integers and an integer target, return indices of the two numbers such that they add up to the target.

// input
int[] data = {1, 3, -1, 5, 8, 10};
int sum = 9;

// output
int[] solution = {0, 4};
public static int[] findSumTwo(int[] data, int sum) {
// iterate until the next to last element
for (int i = 0; i < data.length-1; i++) {
// iterate to the last element, starting from the second element
for (int j = 1; i < data.length; j++) {
// (the double loop will start from the
// {0, 1} index pair and stop iterating at {n-1, n})

// if the elements add up, return their indices
if (data[i]+data[j] == sum) return new int[]{i,j};
}
}

// not found
return new int[]{-1};
}
public static int[] findSumTwo(int[] data, int sum) {
// value->index map
Map<Integer, Integer> seen = new HashMap<>();

// iterate through the array once (O(N))
for (int pos=0; i < data.length; i++) {
// assigning the element for convenience
// because it reads better
int element = data[i];

// if we've already seen the current element
if (seen.containsKey(element)) {
// form a solution
return new int[]{seen.get(element), pos};
}

// otherwise mark its difference as 'seen'
seen.put(sum-element, i);
}

// not found
return new int[]{-1};
}
public static int[] findSumTwo(int[] data, int sum) {
int left=0;
int right=data.length-1;

// only iterate until the positions are valid
// O(N)
while (left < right) {
int found = data[left] + data[right];

if (found == sum) {
// we have found a solution
return new int[]{left, right};
} else if (found < sum) {
// we need a larger number
left++;
} else {
// or a lower one
right--;
}
}

// not found
return new int[]{-1};
}
// most sorting algorithms run in O(N*lgN) time
Arrays.sort(data);
// empty input
int[] data = {};
int sum = /*irrelevant*/;

// null input
int[] data = null;
int sum = /*irrelevant*/;

// overflow
int[] data = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int sum = -2; // doesn't seem correct, but it is given the Integer input

// not enough elements
int[] data = {9};
int sum = 9; // we need at least two elements for a valid solution

// equal elements
int[] data = {8,8};
int sum = 16; // this would cause the first solution to wrongly return {0,0}

// unsorted input
int[] data = {3,1};
int sum = 4; // the correct solution is {0,1}

// no solution
int[] data = {1,1};
int sum = 3; // no pair can sum up to 3

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Mihai Bojin

Software Engineer at heart, Manager by day, Indie Hacker at night. Writing about DevOps, Software engineering, and Cloud computing. Opinions my own.