박종훈 알고리즘 블로그

(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번만 사용하면 되서 시간이 확 줄었다.

(24.04.24 추가) java 풀이 추가

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int _target = target - num;

            if (numMap.containsKey(_target)) {
                return new int[]{numMap.get(_target), i};
            }
            numMap.put(num, i);
        }

        return null;
    }
}

TC, SC

이 풀이의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.

categories: 스터디-알고리즘

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