HelloCho

문제 :

15번 문제는... 아래 링크의 15번 문제와 유사하다 (사실 하루에 다 풀어본건 함정..)

이 문제는 target과 차이가 최소인 조합을 찾는 문제이다.

hellocho.tistory.com/247

해결 방법은 위의 링크와 매우 유사하다.

두 개의 포인터를 이용해서 모든 값을 순회한다.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        diff = float('inf')
        nums.sort()
        for idx,a in enumerate(nums):
            l,r = idx +1, len(nums)-1
            while l < r :
                three_sum = a + nums[l] + nums[r]
                if abs(target - three_sum) < abs(diff):
                    diff = target - three_sum
                if three_sum > target:
                    r -= 1
                else:
                    l += 1
            if diff == 0 :
                break
        return target- diff

l과 r 두개의 포인터를 설정하고 3개의 값을 더한다. target과 three_sum의 차이가 기존의 diff보다 작다면 diff를 바꾼다. 

결과는 아래와 같다.

128ms (O(n^2), 14MB로 통과!