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

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