[Python 으로 푸는 Leetcode]1. Two Sum

느린 개발자·2020년 12월 13일
0

Coding Test

목록 보기
1/21

📌Problem

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]
Output: 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 <= 10310^3
  • 109-10^9 <= nums[i] <= 10910^9
  • 109-10^9 <= target <= 10910^9
  • Only one valid answer exists.

leetcode 에서 풀기


📝Solution

✏️ Brute Force

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] == target:
                    return [i,j]
  • Time complexity : O(N2)O(N^2)

✏️ Hash-table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        hashMap={nums[idx]:idx for idx in range(len(nums))} # {num : index}
        
        for idx in range(len(nums)):
            complement=target-nums[idx]
            if hashMap.get(complement,False) and hashMap.get(complement,False) != idx:
                return [idx,hashMap.get(complement)]           
  • Time complexity : O(N)O(N)
profile
남들보단 느리지만, 끝을 향해

1개의 댓글

comment-user-thumbnail
2021년 12월 22일

I found that solution very popular and helpful:
https://www.youtube.com/watch?v=bsqBECtq7s0&ab_channel=EricProgramming

답글 달기