Solve the Two Sum problem in Python<\/p>\n\n\n\n
\u56de\u7b54<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Here’s a step-by-step approach:<\/p>\n\n\n\n
Here’s the implementation:<\/p>\n\n\n\n
python<\/p>\n\n\n\n
def two_sum(nums, target):\n # Dictionary to store the number and its index\n num_dict = {}\n \n # Iterate through the list\n for i, num in enumerate(nums):\n # Calculate the complement\n complement = target - num\n \n # If the complement exists in the dictionary, return the indices\n if complement in num_dict:\n return [num_dict[complement], i]\n \n # If not, add the current number and its index to the dictionary\n num_dict[num] = i\n \n # If no solution is found, return an empty list or raise an exception\n return [] # or raise ValueError(\"No two sum solution\")\n\n# Example usage\nnums = [2, 7, 11, 15]\ntarget = 9\nresult = two_sum(nums, target)\nprint(result) # Should print [0, 1] because nums[0] + nums[1] == 9<\/pre>\n\n\n\nExplanation:<\/strong><\/p>\n\n\n\n\n- We use a dictionary (num_dict) to keep track of numbers we’ve seen and their indices.<\/li>\n\n\n\n
- As we iterate through the list:\n
\n- We calculate what number, when added to the current number, would give us the target.<\/li>\n\n\n\n
- If this number exists in our dictionary, we’ve found our pair, and we return their indices.<\/li>\n\n\n\n
- If not, we add the current number and its index to the dictionary.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
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.<\/p>\n","protected":false},"excerpt":{"rendered":"