876608. 2 Sum - Find a pair with given sum
2 Sum - Find a pair with given sum
Summary
Given an array nums and a target sum target, find two elements in the array that add up to the target sum. This problem is typically solved using a hash-based approach, leveraging the concept of sorting and iterating through the array.
Detailed Explanation
The problem can be approached by first creating a hash table (in this case, an unordered map) where we store each element from the array as the key and its index as the value. Then, for each target sum calculation, we iterate through the array and check if the difference between the target sum and the current element is present in the hash table.
Here's a step-by-step breakdown of the solution:
- Create an empty unordered map
hashTable. - Iterate through the array
nums. For each element:- Store the element as the key and its index as the value in the
hashTable.
- Store the element as the key and its index as the value in the
- Initialize two pointers,
leftandright, to the start and end of the array. - Calculate the sum of the elements at the
leftandrightindices. - If the calculated sum is equal to the target sum, return the pair of indices.
- If the calculated sum is less than the target sum, increment the
leftpointer. - If the calculated sum is greater than the target sum, decrement the
rightpointer. - Repeat steps 4-7 until the
leftandrightpointers meet or a pair of indices is found.
Time complexity: O(n log n) due to the sorting step. Space complexity: O(n) for storing the hash table.
Optimized Solutions
Here are optimized solutions in various languages:
Java
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashTable = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (hashTable.containsKey(complement)) {
return new int[]{hashTable.get(complement), i};
}
hashTable.put(nums[i], i);
}
return new int[0]; // or throw an exception, depending on the requirements
}