[Leetcode] Array - Two Sum

📄 Description

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, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

💻 My Submission

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(1, len(nums)-i):
                if nums[i]+nums[i+j] == target:
                    return [i, i+j]     

My Solution is based on "Bruet Force" method.
So the Complexity will be like below.

Time Complexity: O(n^2)
Space Complexity: O(1)

But I saw this Problem is hash-taged with "Hash Table", so I looked over the solution using Hashmap.

• solve the problem in linear time.
• using hashmap to store the indices of the elements that are already visited.
• "key" : number of the given input array
• "value" : index of the number in the array represented by the hashmap key

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

Complexity will be like below.

Time Complexity: O(n)
Space Complexity: O(n)

References
https://www.code-recipe.com/post/two-sum