16.最接近的三数之和

题目要求3 <= nums.length <= 1000，则是要求了O(n^2)的解法，类似于三数之和，用双指针法来降低一层复杂度。 为了能用双指针，先排序

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = list(sorted(nums))
        res = target
        min_distance = None
        for i in range(len(nums)):
            new_nums = nums[:i] + nums[i+1:]
            l, r = 0, len(new_nums)-1
            while l < r:
                if nums[i] + new_nums[l] + new_nums[r] == target:
                    return target
                distance = abs(nums[i] + new_nums[l] + new_nums[r] - target)
                if min_distance is None or distance < min_distance:
                    min_distance = distance
                    res = nums[i] + new_nums[l] + new_nums[r]
                if nums[i] + new_nums[l] + new_nums[r] < target:
                    l += 1
                else:
                    r -= 1 
        return res

感觉思路没啥问题，但是只击败了7%的用户

评论