#leetcode

TwoSum.java

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;
        }
    }
}