To solve this problem, we need to find the indices of two numbers in an array such that their sum equals a given target. The solution should be efficient, both in terms of time and space.

Approach

The key insight here is to use a hash map (dictionary) to keep track of the numbers we have seen so far and their indices. This allows us to check for the complement of the current number (i.e., target - current number) in constant time. Here's the step-by-step approach:

1. Initialize a dictionary: This will store the value of each number as the key and its index as the value.
2. Iterate through the array: For each number, compute its complement (target minus the current number).
3. Check for the complement: If the complement exists in the dictionary, return the indices of the complement and the current number.
4. Store the current number: If the complement does not exist, add the current number and its index to the dictionary.

This approach ensures that we only traverse the array once, leading to an O(n) time complexity, where n is the length of the array. The space complexity is O(n) in the worst case, as we might store all elements in the dictionary.

Solution Code

def twoSum(nums, target):
    seen = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], index]
        seen[num] = index
    return []  # According to problem statement, this line is unreachable

Explanation

Let’s break down the solution using an example:

• Example: nums = [2,7,11,15], target =9
  • For index=0 (num=2), complement is 9-2=7 (not in seen → add 2:0 to seen).
  • For index=1 (num=7), complement is 9-7=2 (exists in seen → return [0, 1]).

Another example: nums = [3,2,4], target=6

• index=0 (num=3): complement 3 not in seen → add 3:0.
• index=1 (num=2): complement 4 not in seen → add 2:1.
• index=2 (num=4): complement 2 exists → return [1,2].

This solution handles all edge cases, including negative numbers, zero, and duplicate values (as long as they are different elements). It efficiently finds the solution in linear time, making it optimal for large arrays.

Answer: The function twoSum returns the required indices. For example, if the input is nums = [2,7,11,15] and target=9, the output is [0, 1]. The code is as provided above.

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。