Problem Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Solution

The problem amounts to find the index of a specific number in the rest of array, given an element in the array. The first thought is to use binary search, however, it is used in a sorted array. Though we can first sort it, we will lose the indices at the same time. Another way is to use the HashMap data structure to store the number and its index information. And the method containsKey can be used to check whether the number is in the HashMap. Note we cannot store the full array info in the HashMap first, since the number can appear multiple times. To resolve it, we check the HashMap while we are reading each element from the array. This way, the duplicated elements either are the answers and will be reported, or not the answers and therefore we do not care their infos anymore.

Java Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            if( map.containsKey(target-nums[i]) ){
                return new int[]{ i, map.get(target-nums[i]) };
            }else{
                map.put( nums[i], i );
            }
        }
        return new int[]{0,0};
    }
}