Created
December 4, 2011 03:22
-
-
Save noahlz/1429033 to your computer and use it in GitHub Desktop.
Given an array of integers, determine if any two given elements sum to a given target.
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.TreeMap; | |
import java.util.Map; | |
import java.util.Random; | |
/** | |
* Given an array of integers, determine if any two given elements sum to a given target. | |
*/ | |
public class FindTwoSumToTarget { | |
private static final Random random = new Random(); | |
private static final int RANDOM_INT_RANGE = 20; | |
private static int[] newTestArray(int size) { | |
final int[] arr = new int[size]; | |
for (int i = 0; i < arr.length; i++) { | |
int sign = random.nextInt(3); | |
arr[i] = random.nextInt(100) * (sign % 2 == 0 ? -1 : 1); | |
} | |
return arr; | |
} | |
public static void main(String[] args) { | |
int[] arr = newTestArray(20); | |
System.out.println("Test Array:"); | |
System.out.println(Arrays.toString(arr)); | |
int targetSum = random.nextInt(RANDOM_INT_RANGE) + random.nextInt(RANDOM_INT_RANGE); | |
boolean result = containsSum(arr, targetSum); | |
assert result == containsSumBrute(arr, targetSum) : | |
"Brute force check found a different result from the version that uses a map."; | |
} | |
private static boolean containsSum(int[] arr, int targetSum) { | |
// Using TreeMap just so it will display sorted. | |
Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); | |
for (int i : arr) { | |
Integer val = map.get(i); | |
map.put(i, val == null ? 1 : val + 1); | |
} | |
System.out.println("Analysis: " + map); | |
System.out.println("Target sum: " + targetSum); | |
for(int i : arr) { | |
int compliment = targetSum - i; | |
boolean onlyNeedsOneCount = targetSum != compliment; | |
if(map.containsKey(compliment)) { | |
if(onlyNeedsOneCount || map.get(compliment) > 1) { | |
System.out.println("CONFIRMED: " + i + " + " + compliment + " = " + targetSum); | |
return true; | |
} | |
} | |
} | |
System.out.println("No two integers in the array sum to " + targetSum); | |
return false; | |
} | |
private static boolean containsSumBrute(int[] arr, int target) { | |
for (int i = 0; i < arr.length; i++) { | |
int val = arr[i]; | |
for(int j = 0; j < arr.length; j++) { | |
if(i != j) { | |
if(val + arr[j] == target) { | |
System.out.println("(Brute force check: " + val + " + " + arr[j] + " = " + target + ")"); | |
return true; | |
} | |
} | |
} | |
} | |
System.out.println("(Brute force check confirmed no to integers in the array sum to " + target + ")"); | |
return false; | |
} | |
} |
Author
noahlz
commented
Dec 4, 2011
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment