[Leetcode] Array - Two Sum

김지원·2022년 3월 7일
1

📄 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

profile
Make your lives Extraordinary!

0개의 댓글