https://leetcode.com/problems/3sum-closest/?envType=featured-list&envId=top-google-questions
input :
- nums, target
output :
- 3개의 원소를 더하였을 떄 target과 가장 근접한 값을 출력하시오.
조건 :
Solution explain : Solution1
idea
- nums를 정렬하여 포인터가 이동될 때 마다 target과의 diff를 0을 기준으로 판단하자.
- i는 반복문의 시작점으로 고정 j, k는 i + 1, len(nums) - 1으로 설정.
- j를 키우면 diff가 0보다 커질 수 있고, k를 줄이면 diff가 0보다 작아질 수 있다.
- 더해진 값의 diff_val는 부호가 필요하다
- diff_ret과 비교에서는 절대값으로 비교할 것이기에 abs연산을 수행한다.
주의
- diff_val이 diff_ret와 비교하는지, 포인터의 이동을 위한 비교인지에 따라 부호가 필요한지 없어야 하는지가 달라진다.
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
ret = -float("inf")
diff_ret = abs(ret - target)
for i in range(len(nums) - 2):
j, k = i + 1, len(nums) - 1
while j < k:
val = nums[i] + nums[j] + nums[k]
diff_val = val - target
if abs(diff_val) < diff_ret:
ret, diff_ret = val, abs(diff_val)
if diff_val < 0:
j += 1
else:
k -= 1
return ret
s = Solution()
print(s.threeSumClosest([4,0,5,-5,3,3,0,-4,-5], -2))
print(s.threeSumClosest([1, 1, 1, 0], -100))
print(s.threeSumClosest([1, 1, 1, 0], 100))
print(s.threeSumClosest([-1,2,1,-4], 1))
print(s.threeSumClosest([0, 0, 0], 1))