Leetcode Problem Statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
All the solutions provided below use the same approach. We initialize an empty dictionary or hash map to store the indices of the numbers we have seen so far.
We loop through the array and for each number, we calculate its complement (target – number) and check if the complement exists in our dictionary.
If it does, we return the indices of the current number and its complement. If not, we add the current number and its index to our dictionary and continue with the loop.
The time complexity of this algorithm is O(n) because we loop through the array only once. The space complexity is also O(n) because we need to store the indices of the numbers in the dictionary.
Two sum Python solution
def twoSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict = {}
for i, num in enumerate(nums):
complement = target - num
if complement in dict:
return [dict[complement], i]
dict[num] = iThe solution uses a dictionary (Python’s implementation of a hash map) to store the indices of the numbers we have seen so far. We initialize an empty dictionary with dict = {}.
We loop through the array nums using the enumerate function, which returns a tuple containing the index and value of each element in the array. The loop variable num contains the value of the current element, and i contains its index.
For each num, we calculate its complement complement = target - num. The complement is the value that we need to add to num to get the target sum.
We check if the complement exists in our dictionary using the in keyword. If it does, we return the indices of the complement and the current element as a list.
If the complement does not exist in the dictionary, we add the current element and its index to the dictionary using dict[num] = i. This allows us to look up the index of a complement in constant time.
If we reach the end of the loop without finding a solution, we raise an exception with raise ValueError("No two sum solution").
The time complexity of this solution is O(n) because we loop through the array once, and each dictionary lookup takes constant time on average. The space complexity is also O(n) because we need to store the indices of the numbers in the dictionary.
Two sum Ruby solution
def two_sum(nums, target)
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict = {}
nums.each_with_index do |num, i|
complement = target - num
if dict.key?(complement)
return [dict[complement], i]
dict[num] = i
end
endThe Ruby solution is similar to the Python solution, but it uses the each_with_index method to loop through the array. This method calls the given block with two arguments: the element and its index.
Inside the loop, we calculate the complement complement = target - num and check if it exists in our dictionary using the key? method. If it does, we return the indices of the complement and the current element as an array.
If the complement does not exist in the dictionary, we add the current element and its index to the dictionary using dict[num] = i.
The time complexity of this solution is O(n) because we loop through the array once, and each dictionary lookup takes constant time on average. The space complexity is also O(n) because we need to store the indices of the numbers in the dictionary.
Two sum Java solution
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);
}
throw new IllegalArgumentException("No two sum solution");
}
}The Java solution is similar to the Python and Ruby solutions, but it uses a Map (Java’s implementation of a hash map) instead of a dictionary. We initialize a Map using Map<Integer, Integer> map = new HashMap<>().
We loop through the array using a for loop and calculate the complement complement = target - nums[i]. We check if the complement exists in our Map using the containsKey method. If it does, we return the indices of the complement and the current element as an array.
If the complement does not exist in the Map, we add the current element and its index to the Map using map.put(nums[i], i).
If we reach the end of the loop without finding a solution, we raise an exception with throw new IllegalArgumentException("No two sum solution").
The time complexity of this solution is O(n) because we loop through the array once, and each Map lookup takes constant time on average. The space complexity is also O(n) because we need to store the indices of the numbers in the Map.
Two sum JavaScript solution
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
throw new Error('No two sum solution');
}The JavaScript solution is similar to the Python, Ruby, and Java solutions, but it uses a Map instead of a dictionary or hash map. We initialize a Map using const map = new Map().
We loop through the array using a for loop and calculate the complement const complement = target - nums[i]. We check if the complement exists in our Map using the has method. If it does, we return the indices of the complement and the current element as an array.
If the complement does not exist in the Map, we add the current element and its index to the Map using map.set(nums[i], i).
If we reach the end of the loop without finding a solution, we raise an exception with throw new Error("No two sum solution").
The time complexity of this solution is O(n) because we loop through the array once, and each Map lookup takes constant time on average. The space complexity is also O(n) because we need to store the indices of the numbers in the Map.
