Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input will have at most one solution, and you may not use the same index twice.
In case no solution exists, return [-1, -1]
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
The problem requires us to find two distinct indices in an array such that the numbers at those indices add up to a given target. If no such indices exist, we should return [-1, -1].
nums.target.[-1, -1].Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0] + nums[1] = 2 + 7 = 9
The core challenge is to identify two distinct indices in the array whose corresponding values sum up to the target. This problem is significant in various applications such as financial transactions, inventory management, and more.
Potential pitfalls include assuming multiple solutions or using the same index twice, which the problem explicitly disallows.
To solve this problem, we can start with a naive approach and then discuss optimized solutions.
The naive solution involves checking all possible pairs of indices to see if their corresponding values sum up to the target. This can be achieved using two nested loops.
While the naive solution works, it is not optimal. We can use a hash map to store the difference between the target and each element as we iterate through the array. This allows us to check in constant time if the complement of the current element exists in the hash map.
def two_sum(nums, target):
# Iterate through each pair of indices
for i in range(len(nums) - 1):
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 [-1, -1] if no solution is found
return [-1, -1]
def two_sum(nums, target):
# Create a hash map to store the difference and index
num_map = {}
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement exists in the hash map
if complement in num_map:
return [num_map[complement], i]
# Store the index of the current number
num_map[num] = i
# Return [-1, -1] if no solution is found
return [-1, -1]
def two_sum(nums, target):
# Iterate through each pair of indices
for i in range(len(nums) - 1):
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 [-1, -1] if no solution is found
return [-1, -1]
def two_sum(nums, target):
# Create a hash map to store the difference and index
num_map = {}
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement exists in the hash map
if complement in num_map:
return [num_map[complement], i]
# Store the index of the current number
num_map[num] = i
# Return [-1, -1] if no solution is found
return [-1, -1]
To test the solution comprehensively, we should include a variety of test cases:
def test_two_sum():
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([], 1) == [-1, -1]
assert two_sum([1], 1) == [-1, -1]
assert two_sum([1, 2, 3], 7) == [-1, -1]
print("All test cases pass")
test_two_sum()
Understanding and solving the Two Sum problem is crucial for developing problem-solving skills. It helps in understanding the importance of different approaches and their trade-offs. Practice and exploration of similar problems can further enhance these skills.