[ LeetCode - 16 ] 3Sum Closest

https://leetcode.com/problems/3sum-closest/description/

3Sum Closest - LeetCode

3Sum과 비슷한 문제여서 비슷하게 접근했다.

다만 다른점이라고는 3개의 합이 꼭 일치하지 않아도 가장 가까운 숫자 하나가 return 되어야 한다는 것.

---

[ 📌 풀이 ]

1) 리스트 순회하면서 현재 순회중인 인덱스를 srt(start)로 잡는다.

2) 세 포인터중 가운데 포인터는 mid(middle)은 srt의 바로 다음 포인터에서 시작하고(srt + 1), 마지막 포인터 end는 리스트 마지막 요소로 시작한다.

3) sums와 target을 비교해서 sums의 값을 증가 시키거나 감소시키기 위해서 인덱스를 제어한다.

---

[ 📌 코드 - Python ]

첫 코드는 Runtime이 더 낮았었는데  if sums == target을 추가해주니까 불필요한 연산이 줄어서 시간이 많이 줄었다.

"""
# Author    : Lee In Bok 
# Date      : 2023.10.31(Tue)
# Spend Time: 36m 17s
# Runtime   : 642 ms (Beats 60.70%)
# Memory    : 16.3 MB (Beats 83.53%)
# Algoritm  : Two Pointer
"""

from typing import List
import math

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        ans = math.inf
        nums.sort()

        for srt, num in enumerate(nums):
            mid, end = srt + 1, len(nums) - 1 
            
            while mid < end:
                sums = num + nums[mid] + nums[end]

                if sums == target:
                    return sums

                if abs(sums - target) < abs(ans - target):
                    ans = sums

                if sums < target:
                    mid += 1
                else:
                    end -= 1

        return ans

---

[ 📌 결과 ]

[ Result ]