<--- 리트코드 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(0len(nums) - 1):
    for j in range(i + 1len(nums)):
      if nums[i] + nums[j] == target:
        return [i, j] 
 
nums = [271115]
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 = [271115]
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 = [271115]
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 = [271115]
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 = 0len(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 = [271115]
target = 9
print(two_sum(nums, target))
cs