Created
September 26, 2015 08:38
-
-
Save yrps/0975db59e2846d7502e2 to your computer and use it in GitHub Desktop.
O(n) solutions finding two elements in a series that add to a given sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.HashSet; | |
/** | |
* Demonstrates O(n) solutions to the problem of finding two elements in a series that add to a given sum. | |
* @author ncoop | |
*/ | |
public class TwoSums { | |
/** | |
* Given an unsigned integer array <b>a</b> and a target unsigned integer <b>k</b>, returns a two-element int array | |
* containing two members of a that sum to k. If no such pair exists, returns null. | |
* Throws <code>IllegalArgumentException</code> if <b>k</b> is less than zero. | |
* | |
* Time cost: O(n), Omega(1) | |
* Space cost: O(n), Omega(n) | |
* | |
* @param a An array of ints; negative ints or ints greater than <b>k</b> are ignored | |
* @param k An int to which two members of a should sum | |
* @return an array of two ints from <b>a</b> that sum to <b>k</b>, or null if no pair exists | |
*/ | |
public static int[] twoSumUnsigned(int[] a, int k) { | |
if (k < 0 ) { | |
throw new IllegalArgumentException(); | |
} | |
boolean found[] = new boolean[k+1]; | |
for (int i : a) { | |
if (i >= 0 && i <= k) { | |
if (found[k - i]) { | |
return new int[]{i, k - i}; | |
} | |
found[i] = true; | |
} | |
} | |
return null; | |
} | |
/** | |
* Given an integer array <b>a</b> and a target integer <b>k</b>, returns a two-element int array containing two | |
* members of a that sum to k. If no such pair exists, returns null. | |
* | |
* Time cost: O(n), Omega(1) | |
* Space cost: O(n), Omega(1) | |
* | |
* @param a An array of ints; negative ints allowed | |
* @param k An int to which two members of a should sum | |
* @return an array of two ints from <b>a</b> that sum to <b>k</b>, or null if no pair exists | |
*/ | |
public static int[] twoSum(int[] a, int k) { | |
HashSet<Integer> found = new HashSet<>(); | |
for (int i : a) { | |
if (found.contains(k-i)) { | |
return new int[] {i, k-i}; | |
} | |
found.add(i); | |
} | |
return null; | |
} | |
public static void main(String[] args) { | |
Object[][] testcases = new Object[][]{ | |
{new int[]{0, 1, 7, 3}, 4}, | |
{new int[]{0, 1, 7, 3}, 7}, | |
{new int[]{0, 1, 7, 3}, 5}, | |
{new int[]{2, -2, 9, 3}, 7}, | |
{new int[]{2, -2, 9, 3}, 8}, | |
{new int[]{1, -1, 7, -3}, -4}, | |
{new int[]{}, 1}, | |
{new int[]{1}, 1}, | |
{/* bigArray */}, | |
{/* bigArray */} | |
}; | |
int bigK = 500; | |
int[] bigArray = new int[bigK/2]; | |
for (int i = 0; i < bigK/2; i++) { | |
bigArray[i] = i+1; | |
} | |
testcases[testcases.length-2] = new Object[]{bigArray, bigK-1}; // big array with one solution | |
testcases[testcases.length-1] = new Object[]{bigArray, bigK}; // big array with no solution | |
String twoSumUnsignedSol, twoSumSol; | |
System.out.println(String.format("%30s %16s %10s", "input", "twoSumUnsigned", "twoSum")); | |
for (Object[] testcase : testcases) { | |
try { | |
twoSumUnsignedSol = Arrays.toString(twoSumUnsigned((int[]) testcase[0], (int) testcase[1])); | |
} catch (IllegalArgumentException e) { | |
twoSumUnsignedSol = "negative sum"; | |
} | |
twoSumSol = Arrays.toString(twoSum((int[])testcase[0], (int)testcase[1])); | |
System.out.println(String.format("%30s %16s %10s", | |
Arrays.toString((int[]) testcase[0]) + ", " + testcase[1], twoSumUnsignedSol, twoSumSol)); | |
} | |
} | |
} |
Author
yrps
commented
Sep 26, 2015
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment