Python描述 LeetCode 16. 最接近的三数之和

哈妹 lv.1

发布时间：2022-10-27 12:23:22 307

Python描述 LeetCode 16. 最接近的三数之和

题目

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

解题思路

排序后双指针。先选定一个数，剩余两个数使用双指针遍历，根据三数之和与target大小的比较来确定指针的移动

Python描述

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        m = len(nums)
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
        for i in range(m):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            j, k = i+1, m-1
            while j < k:
                tmp_sum = nums[i] + nums[j] + nums[k]
                res =  res if abs(tmp_sum - target) > abs(res - target) else tmp_sum
                if tmp_sum < target:
                    j += 1
                else:
                    k -= 1
        return

文章来源： https://blog.51cto.com/u_15845758/5795786

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。