leetcode - 最接近的三数之和

leetcode: 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这题在我看来和上一个三数之和差不多，算是一个衍生版吧，那就沿用上题的思路来改进吧

我们先随便写个用不排序的遍历试试

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        rint = 9999999
        rint1 = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    a = nums[i] + nums[j] + nums[k] - target
                    if a >= 0 and a <= rint:
                        rint = a
                        rint1 = a + target
                    elif a < 0 and -a <= rint:
                        rint = -a
                        rint1 = a + target
        return rint1

不出我们所料，他果然超时了，倒在了第67个用例上，然后我们试着排一下序

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        rint = 9999999
        rint1 = 0
        nums.sort()
        for i in range(len(nums)):
            if i == 0 or nums[i] > nums[i-1]:
                if nums[i] - rint > target and nums[i] > 0:
                    break
                for j in range(i+1, len(nums)):
                    if j == i+1 or nums[j] > nums[j-1]:
                        if nums[i] + nums[j] - rint > target and nums[j] > 0:
                            break
                        for k in range(j+1, len(nums)):
                            if k == j+1 or nums[k] > nums[k-1]:
                                if nums[i] + nums[j] + nums[k] - rint > target and nums[k] > 0:
                                    break
                                a = nums[i] + nums[j] + nums[k] - target
                                if a >= 0 and a <= rint:
                                    rint = a
                                    rint1 = a + target
                                elif a < 0 and -a <= rint:
                                    rint = -a
                                    rint1 = a + target
        return rint1

好的倒在了第108个用例上，他尽力了= =，我们再用双指针法试试

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        rint = 9999999
        rint1 = 0
        nums.sort()
        for i in range(len(nums)):
            if i == 0 or nums[i] > nums[i-1]:
                l = i + 1
                r = len(nums) - 1
                while l < r:
                    s = nums[i] + nums[l] + nums[r]
                    a = s - target
                    if a < 0:
                        l += 1
                        if -a < rint:
                            rint = -a
                            rint1 = s
                    elif a > 0:
                        r -= 1
                        if a < rint:
                            rint = a
                            rint1 = s
                    else:
                        rint = 0
                        rint1 = target
                        break;
        return rint1

好的，双指针大法真好用，一次就过了。

这周还要补数据库图形学软工毛概，啊啊啊啊啊啊啊啊，有毒啊，还我周末啊