파이썬 알고리즘 인터뷰 - 09. 세 수의 합

 

<--- 리트코드 15. 3Sum --->

# 문제: 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

 

입력

nums = [-1, 0, 1, 2, -1, 4]

출력

[   [-1, 0, 1],   [-1, -1, 2] ]

 

 

# 풀이

1. 브루트 포스로 계산

def three_sum(nums):
  results = []
  nums.sort()
 
  for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
      continue
    
    for j in range(i + 1, len(nums) - 1):
      if j > i + 1 and nums[j] == nums[j - 1]:
        continue
 
      for k in range(j + 1, len(nums)):
        if k > j +1 and nums[k] == nums[k - 1]:
          continue
          
        if nums[i] + nums[j] + nums[k] == 0:
          results.append((nums[i], nums[j], nums[k]))
 
  return results
 
nums = [-1, 0, 1, 2, -1, 4]
print(three_sum(nums))

 

2. 투 포인터로 합 계산

def three_sum(nums):
  results = []
  nums.sort()
 
  for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
      continue
    
    left, right = i + 1, len(nums) -1
    while left < right:
      sum = nums[i] + nums[left] + nums[right]
      if sum < 0:
        left += 1
      elif sum > 0:
        right -= 1
      else:
        results.append((nums[i], nums[left], nums[right]))
 
        while left < right and nums[left] == nums[left + 1]:
          left += 1
        while left < right and nums[right] == nums [right - 1]:
          right -= 1
 
        left += 1
        right -= 1
        
  return results
 
nums = [-1, 0, 1, 2, -1, 4]
print(three_sum(nums))