To solve this problem, we need to find two distinct elements in an integer array whose sum equals a given target value. The solution should efficiently return the indices of these two elements, ensuring each element is used only once.
Approach
The optimal approach to solve this problem in O(n) time complexity (where n is the number of elements in the array) uses a hash map (dictionary in Python) to store the elements and their indices as we iterate through the array. Here's the step-by-step breakdown:
- Hash Map Initialization: Create an empty dictionary to keep track of elements we've seen so far and their indices.
- Iterate Through Array: For each element in the array:
- Calculate the complement (target value minus the current element).
- If the complement exists in the hash map, return the indices of the complement and the current element (since their sum equals the target).
- If the complement does not exist, add the current element and its index to the hash map.
- Guaranteed Solution: The problem states there is exactly one valid solution, so we don't need to handle cases where no solution is found.
Solution Code
def two_sum(nums, target):
num_map = {}
for index, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], index]
num_map[num] = index
# The problem guarantees exactly one solution, so this line is unreachable
Explanation
- Hash Map Usage: The hash map allows us to look up the complement of the current element in O(1) time, making the overall time complexity O(n).
- Distinct Indices: Since we add elements to the hash map as we iterate, the complement (if found) will always have an index that is earlier than the current element, ensuring we don't reuse the same element (even if values are duplicated, their indices are distinct).
Examples:
- For
nums = [2,7,11,15]andtarget =9, the function returns[0, 1](2+7=9). - For
nums = [3,2,4]andtarget=6, it returns[1, 2](2+4=6). - For
nums = [3,3]andtarget=6, it returns[0,1](3+3=6, distinct indices).
This approach efficiently solves the problem with optimal time and space complexity. The space complexity is O(n) due to the hash map storing up to n elements.
Answer: The Python function two_sum as provided above is the solution. For example, if the input array is [2,7,11,15] and target is 9, the output is [0, 1].
(Note: The exact output depends on the input, but the function correctly returns the indices for any valid input as per the problem statement.)


作者声明:本文包含人工智能生成内容。