Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#leetcode
import java.util.Hashtable;
import java.util.ArrayList;
public class TwoSum {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
if(numbers == null || numbers.length <= 1) return result;
Hashtable<Integer, Integer> freqs = new Hashtable<Integer, Integer>();
Hashtable<Integer, ArrayList<Integer>> indices = new Hashtable<Integer, ArrayList<Integer>>();
// first pass, count the frequency and save the index
for(int i = 0; i < numbers.length; i++){
int current = numbers[i];
if(freqs.containsKey(current)){
freqs.put(current, freqs.get(current) + 1);
indices.get(current).add(i+1);
}else{
freqs.put(current, 1);
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(i+1);
indices.put(current, list);
}
}
// second pass
for(int num: numbers){
if(outOfBound(num, target)) continue;
int remain = target - num;
if(freqs.containsKey(remain)){
if(remain == num){
if(freqs.get(num) >= 2){
result[0] = indices.get(num).get(0);
result[1] = indices.get(num).get(1);
break;
}
}else{
result[0] = indices.get(num).get(0);
result[1] = indices.get(remain).get(0);
break;
}
}
}
return result;
}
private boolean outOfBound(int num, int target){
if(num > 0){
if(Integer.MIN_VALUE + num > target) return true;
return false;
}else{
if(Integer.MAX_VALUE + num < target) return true;
return false;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment