Two Sum

Leetcode Easy

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> hm = new HashMap<>();

        for (int i = 0; i < nums.length; i++){
            int curTgt = target - nums[i];

            // Check if we've already seen the corresponding number
            if (hm.containsKey(curTgt))
                return new int[]{hm.get(curTgt), i};

            hm.put(nums[i], i);
        }

        // Should never reach here per the problem description
        return new int[] {0, 0};
    }
}

How it works

For each number, we put the value in the array, and the corresponding index. We also check for the number that we are looking for and if it is there, we return the two indices.