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:
[11, 2, 6, 15, -1, 10]
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution
We can use one HashMap to store the index of the current value. Later whenever we get a value, we use target - current value as key to lookup the HashMap. If we found it, that is the solution.
import java.util.*;
class Solution {
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 11, 15};
int target = 9;
int[] result = solve(arr, target);
if(result == null) {
throw new RuntimeException("impossible");
}
System.out.println(result[0] + "," + result[1]);
}
//2, 7, 11, 15
private static int[] solve(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < arr.length; i++) {
int other = target - arr[i]; //2
if(map.get(other) != null) {
return new int[]{map.get(other), i};
}
map.put(arr[i], i); //7 0
}
return null;
}
}
The time complexity is O(N) and space complexity is O(N).
