박종훈 기술블로그

(Leetcode) 1 - two sum

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

Facebook 테크리드가 추천하는 Leetcode 문제 76가지 라는 글을 보게되었다.

위 링크를 보고 자극받아 오랜만에 알고리즘 문제를 풀어보았다.
시간 날때 조금씩 풀어봐야겠다 싶다.


two-sum 문제

내가 작성했던 해결책 (2554ms, 18.1MB)

Brute Force 방식

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

솔루션 (53ms, 18.6MB)

One-pass Hash Table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)

        for i in range(n):
            num = nums[i]
            _target = target - num

            if _target in numMap:
                return [numMap[_target], i]
            numMap[num] = i

반복문을 1번만 사용하면 되서 시간이 확 줄었다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Hash Table , Leetcode