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.
Input: An array of integers nums and an integer target.
Output: Indices of the two numbers such that they add up to target.
Constraints:
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
The core challenge of the Two Sum problem is to find two distinct indices in the array such that the numbers at those indices add up to the given target. This problem is significant in various applications, such as financial transactions, where you need to find pairs of transactions that sum up to a specific amount.
Potential pitfalls include assuming that there might be multiple solutions or that the same element can be used twice. Misunderstanding these constraints can lead to incorrect solutions.
To solve the Two Sum problem, we can consider several approaches:
The naive solution involves checking all possible pairs of numbers to see if they add up to the target. This approach has a time complexity of O(n^2) and is not optimal for large arrays.
def two_sum_naive(nums, target):
# Iterate over each pair of elements
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
# Check if the sum of the pair equals the target
if nums[i] + nums[j] == target:
return [i, j]
return None
While this approach is straightforward, it is inefficient for large arrays due to its quadratic time complexity.
A more efficient approach involves using a hash map to store the indices of the elements as we iterate through the array. This allows us to check in constant time whether the complement of the current element (i.e., target - current element) exists in the array.
def two_sum(nums, target):
# Create a hash map to store the indices of the elements
num_to_index = {}
# Iterate over the array
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement is in the hash map
if complement in num_to_index:
return [num_to_index[complement], i]
# Store the index of the current element in the hash map
num_to_index[num] = i
return None
This approach has a time complexity of O(n) and a space complexity of O(n), making it much more efficient for large arrays.
def two_sum_naive(nums, target):
# Iterate over each pair of elements
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
# Check if the sum of the pair equals the target
if nums[i] + nums[j] == target:
return [i, j]
return None
def two_sum(nums, target):
# Create a hash map to store the indices of the elements
num_to_index = {}
# Iterate over the array
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement is in the hash map
if complement in num_to_index:
return [num_to_index[complement], i]
# Store the index of the current element in the hash map
num_to_index[num] = i
return None
Time Complexity: O(n^2) - We need to check all pairs of elements.
Space Complexity: O(1) - No additional space is used.
Time Complexity: O(n) - We iterate through the array once.
Space Complexity: O(n) - We store the indices of the elements in a hash map.
Consider the following edge cases:
Example edge cases:
Input: nums = [-1, -2, -3, -4, -5], target = -8
Output: [2, 4]
Input: nums = [3, 3], target = 6
Output: [0, 1]
To test the solution comprehensively, consider a variety of test cases:
Example test cases:
def test_two_sum():
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([-1, -2, -3, -4, -5], -8) == [2, 4]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([1, 2, 3, 4, 5], 9) == [3, 4]
assert two_sum([0, 4, 3, 0], 0) == [0, 3]
print("All test cases pass")
When approaching such problems, consider the following tips:
In this blog post, we discussed the Two Sum problem, explored both naive and optimized solutions, and provided detailed explanations and code implementations. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for coding interviews. Keep practicing and exploring further to enhance your abilities.