Problem
Given an integer array nums and an integer target, find the indices of the two numbers whose sum equals the target.Each input is guaranteed to have exactly one valid solution, and the same array element cannot be used more than once. The indices may be returned in any order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [2,7,11,15]
target = 9
Output
[0,1]
Solution
This solution uses a HashMap to store each number along with its index.For each element, it calculates the required complement (target - number) and checks whether that complement has already been seen.
If the complement is found, it immediately returns the two indices. Otherwise, it stores the current number and its index in the map and continues scanning the array.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int number = nums[i];
int lookup = target - number;
if (map.containsKey(lookup))
return new int[] { map.get(lookup), i };
map.put(number, i);
}
return new int[] {};
}
Complexity
The algorithm traverses the array only once, and each HashMap lookup or insertion takes O(1) time on average, resulting in an overall time complexity ofO(n). The extra space complexity is
O(n) because the map may store all array elements in the worst case.