(Leetcode) 1 - two sum
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
Facebook 테크리드가 추천하는 Leetcode 문제 76가지 라는 글을 보게되었다.
위 링크를 보고 자극받아 오랜만에 알고리즘 문제를 풀어보았다. 시간 날때 조금씩 풀어봐야겠다 싶다.
내가 작성했던 해결책 (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)이다.