Hash

Hash

1. Two Sum: leetcode.cn/problems/two-sum/

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

• You may assume that each input would have exactly one solution.
• You may not use the same element twice.
• You can return the answer in any order.

Approach and Solution (Hash Map)

Iterate through the array and use a hash map map to store the numbers that have already appeared along with their indices. For the current num, check if its complement target - num has already appeared: if it has, return the indices of both; otherwise, add the current number to the hash map.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}  
        for i, num in enumerate(nums):
            x = target - num
            if x in map:
                return [map[x], i]
            map[num] = i
        return []

Complexity Analysis

• Time Complexity: O(n), as each element is inserted into the table at most once and looked up at most once (amortized O(1)).
• Space Complexity: O(n), in the worst case, the hash map stores all elements.