알고리즘 공부 다시 시작,,,, 가보자고LeetCode 문제 75선 : https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU
LEETCODE 1. Two Sum
-
문제
: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. -
Example 1:
Input: nums = [2,7,11,15], target = 9
Output : [0,1]
Explanation : Because nums[0] + nums[1] == 9, we return [0, 1]. -
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2] -
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1] -
Constraints
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
1차 시도
- 막연하게,,, 1개의 반복문으로 target - nums[i]이 list에 있는지 검사하고 있다면 index()로 인덱스 찾아서 반납하기로 시도
- example 3에서 [0,1]을 반납해야하는데 []를 반납해서 실패
sol) 1. Brute force : O(n^2)
- 2중 반복문으로 nums[i], nums[j] 더해서 target이면
return [i,j]
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return [i,j]sol) 시간복잡도 < O(n^2) => Hash Table
Two-pass Hash Table
class Solution(object):
def twoSum(self, nums, target):
table = {num: i for i, num in enumerate(nums)}
#nums 원소들의 index로 hash table 구성
for i, num in enumerate(nums):
if ((target-num) in table) and (i != table[(target-num)]):
return [i, table[(target-num)]]"두번째 풀이 Two-pass Hash Table은 먼저 for문으로 table이라는 해시 테이블에 nums의 인덱스와 값을 저장한 후 다시 for문을 돌려 table 내에서 원하는 complement 값을 찾는 방식이다."
One-pass Hash Table
class Solution(object):
def twoSum(self, nums, target):
table = {}
for i, num in enumerate(nums):
complement = target - num
if complement in table:
return [i, table[complement]]
else:
table[num] = i"세번째 풀이 One-pass Hash Table은 두번째 풀이처럼 table이라는 해시 테이블에 nums의 인덱스와 값을 저장하지 않고, for문 한번으로 table에 값을 삽입하는 동안 현재 요소의 complement가 이미 존재하는지 확인하며, 이미 존재하는 경우 즉시 리턴을 해주는 방식이다."
<참고>
