欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最接近的三个数的和

程序员文章站 2024-03-16 20:28:34
...
"""
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
题解:
排序+双指针
算法流程:
特判,对于数组长度 l,如果数组为Null或者数组长度小于3,返回 None。
对数组进行排序,并定义min_num,保存最接近和。
遍历排序后数组:
对于重复元素,跳过,避免重复计算(也可以不跳过)
令左指针Left=i+1,右指针R=n-1,当L<R时,执行循环:
*令temp=nums[i]+nums[Left]+nums[Right],如果temp=target,返回target
*若abs(temp-target)<abs(min_num-target)说明temp更接近目标,更新min_num
*若temp-target大于0,说明nums[Right]太大,Right左移
*若temp-target小于0,说明nums[Left]太小,Left右移
"""

class Solution:
    def threeSumClosest(self, nums,target) -> int:
        l = len(nums)
        # 特判,对于数组长度 l,如果数组为Null或者数组长度小于3,返回 None。
        if not nums or l < 3: return None
        nums = sorted(nums)
        min_num = nums[0] + nums[1] + nums[2]
        for i in range(l - 1):
            # 对于重复元素,跳过,避免重复计算(也可以不跳过)
            if (i>0 and nums[i]==nums[i-1]):
                continue
            left, right = i + 1, l - 1
            while left < right:
                temp = nums[i] + nums[left] + nums[right]
                # temp=nums[i]+nums[Left]+nums[Right],如果temp=target,返回target
                if temp == target: return target
                # 若abs(temp-target)<abs(min_num-target)说明temp更接近目标,更新min_num
                if abs(temp - target) < abs(min_num - target):
                    min_num = temp
                # 若temp-target小于0,说明nums[Left]太小,Left右移
                if temp - target < 0:
                    left += 1
                # 若temp-target大于0,说明nums[Right]太大,Right左移
                else:
                    right -= 1
        return min_num
测试:
if __name__ == "__main__":
    s = Solution()
    nums = [-1,2,1,-4]
    target = 1.
    r = s.threeSumClosest(nums,target)
    print(r)