LeetCode - 3Sum Closest
요즘 '파이썬 알고리즘 인터뷰'라는 책을 공부중에 있다.
책에서 공부한 예제를 제외한 다른문제를 leetcode에서 풀어보는 중이다.
3Sum 의 응용문제로 입력받은 list의 값들 중
세 수를 골라 더하여 target에 최대한 가까운 세 수의 합을 구하는 문제이다.
투포인터 알고리즘을 이용하면 현재 index, left, right 이렇게 3개의 값에 접근할 수 있다.
먼저 값을 비교하여 포인터를 이동시키기 위해서는 list를 오름차순으로 정렬시킬 필요가 있으며
이렇게 정렬된 list에서 세 값의 합이 target보다 작으면 left가 +1, target보다 크면
right가 -1 씩 포인터가 이동하는 방식으로 target과의 차이가 제일 작은 세 수의 합을 구한다.
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
result = sys.maxsize
nums.sort()
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
if i > 0 and nums[i] == nums[i - 1]:
continue
while left < right:
tmp = nums[i] + nums[left] + nums[right]
if abs(target - tmp) < abs(target - result):
result = tmp
if tmp == target:
return target
elif tmp < target:
left += 1
elif tmp > target:
right -= 1
return result