動機
3sum的two ptr很重要
Problem
Given an array nums
of n integers 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 = 1Output: 2Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Constraints:
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
Sol
一般來說提到3sum都是用two ptr的解法延伸
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
ret = float('inf')
for i in range(len(nums)):
a, b = i+1, len(nums)-1
while a < b:
cnt = sum([nums[x] for x in [i,a,b]])
if cnt == target:
return cnt
else:
ret = min([ret,cnt],key=lambda x: abs(x-target))
if cnt > target:
b -= 1
else:
a += 1
return ret