Cracking LeetCode's Two Sum with a Java HashMap: A Simple and Efficient Approach
The LeetCode "Two Sum" problem is a classic interview question that tests your understanding of basic data structures and algorithms. In this article, we'll explore a clean and efficient Java solution using a HashMap, breaking down the logic and providing a step-by-step guide for implementation.
The Problem:
Given an array of integers nums and a target integer target, find the indices of the two numbers in nums that add up to target. You can assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Original Code:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return new int[0];
}
}
Understanding the Solution:
The core of this solution lies in using a HashMap to store the elements of the array and their corresponding indices. This allows for efficient lookups when searching for the complement (the number needed to reach the target).
Step-by-Step Breakdown:
- Initialize a HashMap: Create a HashMap named
mapto store the elements and their indices. - Iterate through the array: Traverse the input array
nums. - Calculate the complement: For each element
nums[i], calculate the complementcomplement = target - nums[i]. - Check for complement in the map: Use
map.containsKey(complement)to determine if the complement already exists in the map. If it does, you've found the two numbers that add up to the target. - Return the indices: If the complement is found, return an array containing the indices of the complement (retrieved from the map) and the current element (
i). - Add the element to the map: If the complement isn't found, add the current element (
nums[i]) and its index (i) to the map. - Handle no solution case: If the loop completes without finding a solution, return an empty array.
Why HashMap is a Good Choice:
HashMaps are ideal for this problem because they offer constant time average-case performance for operations like insertion and lookup. This efficiency is crucial for a problem that involves finding pairs within a larger array.
Additional Insights:
- This solution has a time complexity of O(n), making it very efficient for large datasets.
- This approach is space-efficient as it only stores elements and their indices in the HashMap, consuming memory proportional to the number of elements in the array.
- The use of HashMap simplifies the logic and eliminates the need for nested loops, making the code more concise and readable.
Conclusion:
Utilizing a HashMap is an elegant and efficient approach to solve the LeetCode Two Sum problem in Java. By leveraging the HashMap's ability to provide fast lookups, you can effectively determine the indices of the two numbers that add up to the target. Understanding this solution helps you grasp the power of HashMaps in solving common algorithmic problems.
