How to Solve Two-Sum in Java

The challenge

Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple like so: (index1, index2).

For the purposes of this challenge, some tests may have multiple answers; any valid solutions will be accepted.

The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; the target will always be the sum of two different items from that array).

twoSum [1, 2, 3] 4 === (0, 2)
Code language: Java (java)

The solution in Java code

Option 1:

public class Solution { public static int[] twoSum(int[] numbers, int target) { for (int i=0; i<numbers.length; i++) for (int j=0; j<numbers.length; j++) if (i!=j && (numbers[i]+numbers[j]==target)) return new int[] {i, j}; return new int[] {0,0}; } }
Code language: Java (java)

Option 2:

import java.util.Arrays; public class Solution { public static int[] twoSum(int[] numbers, int target) { Arrays.sort(numbers); int j = 0; for (int i = 0; i < numbers.length; i++) { j = Arrays.binarySearch(numbers, i, numbers.length, target-numbers[i]); if (j > -1) return new int[] {i, j}; } return null; } }
Code language: Java (java)

Option 3:

import java.util.*; public class Solution { public static int[] twoSum(int[] numbers, int target) { Map seenValues = new HashMap(); for (int i = 0; i < numbers.length; i++) { if (seenValues.containsKey(target - numbers[i])) return new int[]{(int)seenValues.get(target - numbers[i]), i}; seenValues.put(numbers[i], i); } return null; } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNotNull; import static org.junit.Assert.assertTrue; import org.junit.runners.JUnit4; public class TwoSumTest { @Test public void basicTests() { doTest(new int[]{1,2,3}, new int[]{0,2}); doTest(new int[]{1234,5678,9012}, new int[]{1,2}); doTest(new int[]{2,2,3}, new int[]{0,1}); } private void doTest(int[] numbers, int[] expected) { int target = numbers[expected[0]] + numbers[expected[1]]; int[] actual = Solution.twoSum(numbers, target); if ( null == actual ) { System.out.format("Received a null\n"); assertNotNull(actual); } if ( actual.length != 2 ) { System.out.format("Received an array that's not of length 2\n"); assertTrue(false); } int received = numbers[actual[0]] + numbers[actual[1]]; assertEquals(target, received); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments