Python
파이썬 알고리즘 인터뷰 - 07. 두 수의 합
s코딩초보s
2022. 1. 11. 21:51
<--- 리트코드 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 |