Solve the Two Sum problem in Python

Solve the Two Sum problem in Python

回答

Certainly, I’ll provide a solution to the Two Sum problem in Python. This problem is a common interview question where you’re given an array of integers and a target sum, and you need to find two numbers in the array that add up to the target.

Here’s a step-by-step approach:

1. Use a Hash Map: This approach allows for O(n) time complexity, where n is the number of elements in the array.
2. Iterate Through the Array: For each number, calculate what the other number should be to reach the target sum.
3. Check if the Complement Exists: If the complement exists in the hash map, return the indices of both numbers.

Here’s the implementation:

python

def two_sum(nums, target):
    # Dictionary to store the number and its index
    num_dict = {}
    
    # Iterate through the list
    for i, num in enumerate(nums):
        # Calculate the complement
        complement = target - num
        
        # If the complement exists in the dictionary, return the indices
        if complement in num_dict:
            return [num_dict[complement], i]
        
        # If not, add the current number and its index to the dictionary
        num_dict[num] = i
    
    # If no solution is found, return an empty list or raise an exception
    return []  # or raise ValueError("No two sum solution")

# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # Should print [0, 1] because nums[0] + nums[1] == 9

Explanation:

• We use a dictionary (num_dict) to keep track of numbers we’ve seen and their indices.
• As we iterate through the list:
  • We calculate what number, when added to the current number, would give us the target.
  • If this number exists in our dictionary, we’ve found our pair, and we return their indices.
  • If not, we add the current number and its index to the dictionary.

This solution ensures that we only traverse the list once, making it efficient with a time complexity of O(n). The space complexity is also O(n) in the worst case where all numbers are unique.