Posted on by linyf915

[LeetCode] 16. 3Sum Closest

https://leetcode.com/problems/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.
Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Github Solution

#time: O(n^2), space: O(1)
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:
            return
        nums = sorted(nums)
        min_diff = sys.maxsize
        result = 0
        for idx in range(len(nums)-2):
            left = idx + 1
            right = len(nums)-1
            while left < right:
                total = nums[left] + nums[right] + nums[idx]
                if  total == target:
                    return nums[left] + nums[right] + nums[idx]
                if abs(total - target) < min_diff:
                    min_diff = abs(total - target)
                    result = total
                if nums[left] + nums[right] < target - nums[idx]:
                    left += 1
                elif nums[left] + nums[right] > target - nums[idx]:
                    right -= 1
        return result

解法：

  1. 跟3sum一樣，先sort
  2. result = 先挑第一個＋第二個＋最後一個
  3. 比較小，low++, 比較大，high–
  4. 再比較是否跟target的差距更小，是的話換掉result

發表留言