16.md

16. 3Sum Closest

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).

Thinking

nums = [-1,2,1,-4], target = 1

[-4   -1   1     2]   sum: -3, diff: 4
  ^i   ^left     ^right
[-4   -1   1     2]   sum: -1, diff: 3
  ^        ^     ^ 
[-4   -1   1     2]   sum: 2,  diff: 0
       ^   ^     ^ 

nums = [-6,-3,-1,2,3,5]      target = 5

-6  -3  -1  2  3  5      sum = -4, diff = 9
 ^   ^            ^    
-6  -3  -1  2  3  5      sum = -2, diff = 7
 ^       ^        ^  
-6  -3  -1  2  3  5      sum = 1,  diff = 4
 ^          ^     ^  
-6  -3  -1  2  3  5      sum = 2,  diff = 3
 ^             ^  ^  
-6  -3  -1  2  3  5      sum = 1,  diff = 3
     ^   ^        ^  
-6  -3  -1  2  3  5      sum = 4,  diff = 1
     ^      ^     ^  
-6  -3  -1  2  3  5      sum = 5,  diff = 0
     ^         ^  ^  

• 计算 3 数之和（sum）与 target 之间的差值 diff（target - sum = diff），只有小于 diff 时，diff 才更新，如果完全匹配（diff 等于 0）就可以直接返回，否则计算完所有情况后，返回最接近 sum（target - diff）
• 不管是左移还是右移，sum 都是变小？右移变大，左移变小
• 因为 target 不是 0，所以不能指定 i 小于 0，i 可能为整个数组。
• 时间复杂度：O(N^2)，i 为 N，左右指针为 N
• 空间复杂度，O(N)，每次 i 是，都需要一个常数个额外空间存放常量

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        diff = float('inf') # infinite，无限的上限值，用来寻找最小数，因为 int 只能存放整数，float 可以存放 +/-infinity, +/- 0, and "NaN"
        nums.sort()
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                new_diff = target - sum
                if abs(new_diff) < abs(diff):
                    diff = new_diff
                if sum < target:
                    left += 1
                else:
                    right -= 1
            if diff == 0:
                break
        return target - diff

Test

[1,1,1,1] 0

[-1,2,1,-4] 1

[1,1,1,0] -100