1. Two Sum

[zeikar]

Problem link

https://leetcode.com/problems/two-sum

Problem Summary

배열에서 두 개의 합이 target이 되는 두 인덱스를 구하는 문제.

Solution

O(n^2) 풀이는 너무 쉬우므로 O(n) 풀이를 보자.

먼저 2개의 합을 구한다는 것은 하나를 골랐으면 다른 수는 자동으로 정해진다는 것이다.
즉, nums[i] 를 골랐다면 다른 수는 무조건 target - nums[i] 이어야 한다.
여기서 hashmap으로 target-nums[i]를 상수 시간 안에 구할 수 있다면 문제를 O(n)으로 풀 수 있다.

nums[i] 값을 키로 넣고 값으로 i 를 넣게 만들어주면 되는데, 앞에서 하나씩 넣으면서 돌리면 된다.

Source Code

from typing import List


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