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.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> lookup = new HashMap<>();
for(int index = 0; index < nums.length; index++) {
int complement = target - nums[index];
if(lookup.containsKey(complement)){
return new int[] { lookup.get(complement), index };
}
lookup.put(nums[index], index);
}
return null;
}
}
The above Java solution is for the "Two Sum" problem. It utilizes a HashMap to store encountered numbers along with their indices for efficient lookup. The code is quite clear and follows the same logic to achieve O(n) time complexity. Here's a breakdown of how the code works:
lookup
to store encountered numbers as keys and their indices as values.nums
, using an index to keep track of the current position.lookup
HashMap using lookup.containsKey(complement)
. If it does, it means you've found the pair of numbers that add up to the target.lookup
HashMap using lookup.get(complement)
and the current index.lookup
HashMap.null
to indicate that no valid pair was found.Overall, code effectively solves the "Two Sum" problem with an optimal time complexity using a HashMap to store and look up numbers and their indices efficiently.