<--- 리트코드 1. Two Sum --->
# 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.
입력
num = [2, 7, 11, 15], target = 9 |
출력
[0, 1] |
# 풀이
1. 브루트 포스로 계산
1
2
3
4
5
6
7
8
9
|
def two_sum(nums, target):
for i in range(0, len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
|
cs |
2. in을 이용한 탐색
1
2
3
4
5
6
7
8
9
10
|
def two_sum(nums, target):
for i, n in enumerate(nums):
complement = target - n
if complement in nums[i + 1:]:
return nums.index(n), nums[i + 1:].index(complement) + (i + 1)
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
|
cs |
3. 첫 번째 수를 뺀 결과 키 조회
1
2
3
4
5
6
7
8
9
10
11
12
|
def two_sum(nums, target):
nums_map = {}
for i, num in enumerate(nums):
nums_map[num] = i
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target - num]:
return nums.index(num), nums_map[target - num]
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
|
cs |
4. 조회 구조 개선
1
2
3
4
5
6
7
8
9
10
|
def two_sum(nums, target):
nums_map = {}
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target - num], i]
nums_map[num] = i
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
|
cs |
5. 투 포인트 이용 (풀이 불가)
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def two_sum(nums, target):
left, right = 0, len(nums) - 1
while not left == right:
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
return left, right
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
|
cs |
'Python' 카테고리의 다른 글
파이썬 알고리즘 인터뷰 - 09. 세 수의 합 (0) | 2022.01.12 |
---|---|
파이썬 알고리즘 인터뷰 - 08. 빗물 트래핑 (0) | 2022.01.12 |
파이썬 알고리즘 인터뷰 - 06. 가장 긴 팰린드롬 부분 문자열 (0) | 2022.01.10 |
파이썬 알고리즘 인터뷰 - 05. 그룹 에너그램 (0) | 2022.01.10 |
파이썬 알고리즘 인터뷰 - 04. 가장 흔한 단어 (0) | 2022.01.10 |