a different solution in Java with 1 iteration and O(n)


  • 0
    E

    My thoughts:
    the question becomes: if I am at index i, with value nums[i], in this array, does it exists an int with value target-nums[i] ?

    So using hashmap could help solve the problem: the key in the map will be the 'other' int that will add up to the target, and the value is my current index.

    at any iteration j, I will first check if the map contains nums[j], if yes, that mean there was 'another' int in the previous iteration, that is looking for 'me (nums[j])' that adds up to target, and I know the 'other' int, its index is map.get(nums[j]).

    if the map does not contain nums[j], that means the 'other' int did not show up yet, so I will store the int that nums[j] is looking for in the map as the key: target-nums[j], and the current index j as value.
    So that next time, when the 'other' int finds 'me', it knows my index.

    public int[] twoSum(int[] nums, int target) {
            int[] res = new int[2];
            if (nums.length == 0) return res;
            //here the key is the different between the target and current value, and the value is the index of current value
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i=0; i<nums.length; i++) {
    //if not null, this means in previous iteration, there was a match
                if (map.get(nums[i]) != null) {
                    res[0] = map.get(nums[i]); //in order, the previous value index goes in first
                    res[1] = i; //then the value of current index
                    return res;
                } else {
    //no match, we put the (diff, index) in the map
                    map.put(target-nums[i], i);
                }
            }
            return res;
        }
    

Log in to reply
 

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