美文网首页Leetcode
[Leetcode]16. 最接近的三数之和

[Leetcode]16. 最接近的三数之和

作者: LeeYunFeng | 来源:发表于2019-03-06 23:40 被阅读0次

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
    例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

    我的办法:
    总体的思路是排序+双指针,时间复杂度为O(N^2)
    首先,依然是将三个整数求和的问题,转换为两个整数求和。对于nums中的每一个数nums[i],如果剩余数组中存在两个整数nums[j]和nums[k],使得nums[j]+nums[k]最接近target-nums[i]即可。
    其次,对nums排序必然会有助于提升最终求解的效率。假设对nums由小到大排序,则当我们求解最接近target-nums[i]的nums[j]+nums[k]时,可以分为以下三种情况:

    1. nums[j]+nums[k]==target-nums[i],直接return[i,j,k]
    2. nums[j]+nums[k]>target-nums[i],k-=1。
    3. nums[j]+nums[k]<target-nums[i],j+=1。

    每一步都记录下当前的diff=abs(target-nums[i]-nums[j]-nums[k]),如果当前step的diff小于前一步的diff,则记录下该更小的diff及相应的ans。在计算时应当保证j<k。
    虽然思路想得比较清楚,但实现时还是出了问题。主要是没有处理好当前为止最小diff及相应ans的记录。
    执行用时: 148 ms, 在3Sum Closest的Python提交中击败了31.28% 的用户。内存消耗: 10.9 MB, 在3Sum Closest的Python提交中击败了1.02% 的用户。

    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            # 异常处理
            if len(nums)<3:
                return 0
            # 数组排序
            nums=sorted(nums)
            l=len(nums)
            ans=0
            pre_diff,pre_ans=2**31-1,2**31-1
            # 将三数之和转化为两数之和问题
            for i in range(l-2):
                j,k=i+1,l-1
                min_ans=nums[i]+nums[j]+nums[k]
                min_diff=target-min_ans
                # 采用双指针处理
                while j<k:
                    ans=nums[i]+nums[j]+nums[k]
                    diff=target-ans
                    if diff<0:
                        k-=1
                    elif diff>0:
                        j+=1
                    else:
                        return ans
                    if j<k and abs(target-nums[i]-nums[j]-nums[k])<abs(diff):
                        min_ans=nums[i]+nums[j]+nums[k]
                        min_diff=target-min_ans
                        tmp=[nums[i],nums[j],nums[k]]
                if abs(min_diff)<abs(pre_diff):
                    pre_diff=min_diff
                    pre_ans=min_ans
            return pre_ans
    

    别人的方法:
    从思路上看,以下方法并无任何不同,也是采用排序+双指针的方法处理。但编码更为简洁,可以借鉴。
    其中主要的不同点在于:

    1. 我记录了两层循环内各自的最小diff,而以下方法只记录了全局的最小diff,显然后者要更简洁一些。
    2. 以下方法对nums中连续数字相同的情况做了处理,跳过了nums[i] = nums[i - 1]的数据,简化了整个处理过程。
    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            nums.sort()
            comp = 9999999
            myans = 0
            leng = len(nums)
            for i, item in enumerate(nums):
                f = i + 1
                r = leng - 1
                if (i == 0 or nums[i] != nums[i - 1]):
                    while (f < r):
                        ans = nums[i] + nums[f] + nums[r]
                        comptmp = ans - target
                        x = abs(comptmp)
                        #找最接近的
                        if (x < comp):
                            comp = x
                            myans = ans
                        #双指针移动
                        if (comptmp == 0): return myans
                        elif (comptmp < 0): f += 1
                        else: r -= 1
    
            return myans
    

    以下是我参照上述思路改写的版本,效果果然好了很多。执行用时: 68 ms, 在3Sum Closest的Python提交中击败了92.11% 的用户。内存消耗: 10.9 MB, 在3Sum Closest的Python提交中击败了1.02% 的用。

    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            # 异常处理
            if len(nums)<3:
                return 0
            # 数组排序
            nums=sorted(nums)
            l=len(nums)
            base_diff,base_ans=2**31-1,2**31-1
            # 将三数之和转化为两数之和问题
            for i in range(l-2):
                j,k=i+1,l-1
                # 采用双指针处理
                if (i==0 or nums[i]!=nums[i-1]):
                    while j<k:
                        ans=nums[i]+nums[j]+nums[k]
                        diff=target-ans
                        # 如果diff更小,则记录下来
                        if abs(diff)<abs(base_diff):
                            base_diff=diff
                            base_ans=ans
                        if diff<0:
                            k-=1
                        elif diff>0:
                            j+=1
                        else:
                            return ans
            return base_ans         
    

    相关文章

      网友评论

        本文标题:[Leetcode]16. 最接近的三数之和

        本文链接:https://www.haomeiwen.com/subject/gdofpqtx.html