leetcode16 -- 3Sum Closest

leetcode16 -- 3Sum Closest

题目

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:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


现在比刚才的那个又难了一些,这次是返回和目标值绝对值最小的三个数的和,其实和之前15题的思路有很多相似的地方,这时候要不断地更新这个最小的绝对值,然后这时候不再是直接找target了,而是直接去与target比较来判断是该左边的往右移,还是右边的往左移。

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        closest = sum(nums[:3])
        diff = abs(closest-target)
        
        nums.sort()
        for i in range(len(nums)-2):
            left = i+1
            right = len(nums)-1
            
            while left<right:
                summ = nums[i]+nums[left]+nums[right]
                
                new_diff = abs(summ-target)
                if new_diff < diff:
                    diff = new_diff
                    closest = summ
                
                if summ<target:
                    left += 1
                else:
                    right -= 1
                    
        return closest

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦