Leetcode 1. Two Sum (Hash Table)

Leetcode 1. Two Sum (hash table) github: https://github.com/Jasondecode2020/Letscode The idea behind using a hash table for this problem is to iterate through the array and, at each step, check if the complement of the current element (i.e., target - current_element) is already in the hash table. If it is, then you have found the two elements that sum up to the target. class Solution: def twoSum(self, nums, target): for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] method 2: O(n) dict Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity? 1 Prepare a dictionary, use only one loop 2 Use enumerate of index and values of nums array 3 Check is the numbers in the dict or not class Solution: def twoSum(self, nums, target): d = {} for idx, val in enumerate(nums): res = target - val if res in d: return [d[res],idx] else: d[val] = idx test: nums = [2,7,11,15] target = 9 1st loop: d = {}, idx = 0, val = 2, res = 7, 7 is not in d = {}, d = {2: 0} 2nd loop: d = {2: 0}, idx = 1, val = 7, res = 2, 2 is in d = {2: 0}, return [d[2], 1], d[2] = 0 In order to get less than O(n^2) time complexity, we need to prepare a dict, increase a bit memory, but decreased time complexity