O(n) solution with HashMap


  • 1
    C

    Instead of storing the number in the hashMap, store the remainder after subtracting from the target. Works on an unsorted array as well. First look for the number in the hashmap and then store it, so this can handle duplicates as well.
    Example: input is {2,7,4,4} and target is 8.
    i=0 : 2 : HashMap looks like 6->0
    i=1 : 7 : HashMap looks like {6->0, 1->1}
    i=2 : 4 : HashMap looks like {6->0,1->1,4->2}
    i=3 : 4: HashMap already has an entry of 4->2
    hence index1 = (value of key 4 +1) = (2+1) =3
    and index2 = (current i +1 ) = 3+1 = 4
    Hence, index1=3 and index2=4

    private int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int[] result = new int[2];
        for(int i=0; i< nums.length; i++) {
            int rem = target - nums[i];
            if(map.containsKey(nums[i])) {
                result[0] = map.get(nums[i]);
                result[1] = (i+1);
                return result;
            } else
               map.put(rem, i+1);
        }
        return result;
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.