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 []