The Question
CodingTwo Sum
Given an array of integers and a target sum, return the indices of the two distinct elements that add up to the target. Assume exactly one valid answer exists.
Java
HashMap
Questions & Insights
Thinking Process
Complement Search: Instead of iterating through all possible pairs, we can rephrase the problem: for every number
x at index i, we need to find if there exists a number y (where y = target - x) that we have already encountered.Efficient Lookup: To avoid nested loops, we use a Hash Map to store elements we've seen so far. This reduces the search time for the "complement" from O(n) to O(1) on average.
Single Pass Optimization: We can populate the map and check for the complement in a single iteration. If the complement exists in the map, we immediately return the current index and the stored index.
Implementation Breakdown
Problem Set
Functional Requirements: Find two distinct indices
i and j such that nums[i] + nums[j] == target.Constraints:
Exactly one solution exists.
2 \le \text{nums.length} \le 10^4.
-10^9 \le \text{nums[i]} \le 10^9.
-10^9 \le \text{target} \le 10^9.
Approach
Algorithm: Single-pass Hash Map.
Data Structure:
HashMap<Integer, Integer> where Key = value in nums and Value = index of that value.Complexity:
Time: O(n) since we traverse the list containing n elements only once.
Space: O(n) to store up to n elements in the hash map.