Untitled

class Solution {

    /**
    
        [2, 7, 11, 5] -> 9

        9 - 2

        Example:
        2 -> look for 9 - 2 = 7 in the list 

        Brute force, do this for each element-- bleh -> O(n^2)

        Optimize -> 
        iterate once
        put the numbers in a hash map against indices containing that number
        iterate again, find the remaining value in the set
    

     */
    public int[] twoSum(int[] nums, int target) {
        final Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) { 
            if (valueToIndices.containsKey(nums[i])) {
                final List<Integer> existingIndices = 
                    valueToIndices.get(nums[i]);
                existingIndices.add(i);
                valueToIndices.put(nums[i], existingIndices);
            } else {
                List<Integer> newList = new ArrayList<>();
                newList.add(i);
                valueToIndices.put(nums[i], newList);
            }
            
        }
        int result[] = new int[2];

        for (int i = 0; i < nums.length; i++) { 
            int value = nums[i];
            if (valueToIndices.containsKey(target - value)) {
                final List<Integer> indicesWithThisValue = 
                    valueToIndices.get(target - value);
                for (Integer otherIndex: indicesWithThisValue) {
                    if (!otherIndex.equals(i)) {
                        result[0] = i;
                        result[1] = otherIndex;
                        return result;
                    }
                }
            }
            
        }
        return result;

    }
}