문제 링크: https://leetcode.com/problems/two-sum/
1. 문제 파악
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.
직관적으로 해석하자면, nums라는 배열과 target이라는 값을 인자로 받고 nums의 i번째 값과 j번째 값의 합이 target 값과 같을시 [i,j]을 리턴하는 함수를 만들라는 것이다.
1-1. 조건
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.nums 배열의 길이(=인자값의 갯수)는 2 이상 103 이하이다.
nums 배열의 인덱스값은 -109 이상 109 이하이다.
target 값은 -109 이상 109 이하이다.
1-2. 예제
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]2. 풀이
먼저, 나의 풀이를 한번 살펴보겠다.
2-1. 나의 풀이
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
break_check = False
for i in range(1, len(nums)):
for j in range(i):
if nums[i] + nums[j] == target:
break_check = True
return [i,j]
break
if break_check:
break- 이중 for문을 활용하여 배열을 두 번 순회한다.
- if문을 활용하여 순회중 더한 배열 값과 target 값이 같으면 리턴을 해준다.
버블 정렬과 비슷하게 비효율적인 시간복잡도를 가진다.
2-2. LeetCode Solution
자 이제 LeetCode의 solution들을 분석해보겠다.
1. Brute Force
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]첫번째 풀이 Brute Force는 내가 푼 방식과 매우 유사하다.
2. Two-pass Hash Table
class Solution(object):
def twoSum(self, nums, target):
table = {num: i for i, num in enumerate(nums)}
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 값을 찾는 방식이다.
3. 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가 이미 존재하는지 확인하며, 이미 존재하는 경우 즉시 리턴을 해주는 방식이다.
