Array & Hashing
01. Two Sum
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Examples
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
Follow-up
Can you come up with an algorithm that has less than O(n^2) time complexity?
from typing import List
class Solution:
def two_sum(self, nums: List[int], target: int) -> List[int]:
hash_map: dict[int, int] = {} # stores num -> index
for i, num in enumerate(nums):
complement: int = target - num # value needed to reach target
if complement in hash_map:
# Already seen the complement, return both indices
return [hash_map[complement], i]
# Otherwise, store this number and its index
hash_map[num] = i
if __name__ == "__main__":
solution = Solution()
nums = [11,15,2,7]
target = 9
result = solution.two_sum(nums, target)
print(result)Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help