Python第18题:最接近的三数之和【leetcode】

编程试题：

给你一个长度为 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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

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

去年写的代码：

import itertools

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        # 生成三个数的所有组合
        result = list(itertools.combinations(nums, 3))
        sumList = []
        resList = []
        # 求出所有三个数的和，并将其和target的差值加入到和列表里。同时将绝对值加入到另外一个列表里
        for i in result:
            sum = int(i[0]) + int(i[1]) + int(i[2]) - target
            sumList.append(sum)
            resList.append(abs(sum))
        if len(sumList) == 1:
            return sumList[0] + target
        # 找到resList列表里的最小值，然后找到在resList中的索引，该索引对应的就是最接近的值
        resindex = resList.index(min(resList))
        return sumList[resindex] + target

# 获取输入, 类型为字符串
nums = list(map(str, input().split(",")))
target = int(input())
# 调用函数
print(Solution().threeSumClosest(nums,target))

这部分代码时间复杂度较高，在leetcode上执行照旧是无法通过的

学习了双指针以后写的代码：

双指针内容可以参考前两篇文档

可编辑代码如下：

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        numlen = len(nums)
        if numlen == 3:
            return sum(nums)
        nums.sort()
        best = -10001
        for i in range(0, numlen - 2):
            start, end = i + 1, numlen - 1
            while (start < end):
                sumRes = nums[i] + nums[start] + nums[end]
                if sumRes == target:
                    return target
                elif sumRes > target:
                    if abs(sumRes - target) < abs(best):
                        best = sumRes - target
                    end -= 1
                else:
                    if abs(sumRes - target) < abs(best):
                        best = sumRes - target
                    start += 1
        return best + target

# 调用函数
print(Solution().threeSumClosest([10,20,30,40,50,60,70,80,90],1))

提交结果如下，执行不会出现超时的现象了，不过目前仅击败了36%，说明还有进一步优化的空间