Leetcode 16. 3Sum Closest

문제

Given an integer array nums of length n and an integer target, 
find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

주어진 정수 배열에 대해 3개의 숫자를 뽑았을때, 세 숫자의 합과 주어진 타겟 값과의 차이가 가장 작은
세 숫자의 합을 리턴하시오.

예시

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: 타겟값인 1에 가장 가까운 세 숫자는 [-1, 2, 1] 이며, 이 숫자들의 합은 -1 + 2 + 1 = 1 이다.

제한

• $3 <= nums.length <= 500$
• $-1000 <= nums[i] <= 1000$
• $-104 <= target <= 104$

풀이

세 숫자를 오름차순이라 가정하고 left, mid, right 라 명명하고 풉니다.

1. 일단 주어진 nums를 오름차순으로 정렬합니다.
2. 이후 가장 왼쪽부터 오른쪽에 2개의 숫자를 남겨둔 자리까지 left를 정하고 for loop를 돌립니다.
3. 이후 left로부터 오른쪽에 위치한 모든 숫자를 일종의 부분배열로 삼아 본 부분배열의 왼쪽 끝과 오른쪽 끝을 각각 mid, right 로 정합니다.

-5, -3, 1, 2, 4 의 배열에 target이 3인 경우 예시는 아래와 같습니다.

• 주어진 경우에서 left + mid + right 는 -5 + -3 + 4 로 -4 입니다.
• 일단 이 합으로 가장 가까운 합을 갱신합니다.
• 근데 구해진 세 값의 경우 타겟보다 작습니다. 근데 nums는 이미 정렬되어 있기 때문에 mid를 오른쪽으로 한칸 옮기면 반드시
  세 수의 합은 같거나 커질수밖에 없게 됩니다.
• 즉, target에 무조건 가까워지는 방향으로 세 수가 정해지게 되는 것입니다. 한번 옮겨 보겠습니다.
  
• 이 경우 세 수의 합은 -5 + 1 + 4 로 0이 됩니다. 이렇게 차이가 0이 날 경우 그냥 나옵니다.
• 0인 경우가 발견되지 않을시 이후 갱신된 합을 리턴하면 됩니다.

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

        left = 0

        ans = 0
        difference = 999999

        for left in range(0, len(nums) - 2):
            mid, right = left + 1, len(nums) - 1
            while mid < right:
                p_sum = nums[left] + nums[mid] + nums[right]
                diff = abs(target - p_sum)
                
                if diff < difference:
                    difference = abs(target - p_sum)
                    ans = p_sum

                if target - p_sum < 0:
                    right -= 1
                elif target - p_sum > 0:
                    mid += 1
                else:
                    return p_sum

        return ans