Leetcode 16 最接近的三数之和

最接近的三数之和

题目

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

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

解答

思路：
- 首先对输入的数组进行排序；
- 接着固定一个数，对固定数右侧的剩余数组使用双指针进行遍历，期间考虑数组有序通过移动指针逼近target；
- 同时对已经遍历过的相同数字进行跳过，达到剪枝的目的。
- 此处有图解 => https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/

代码：

def threeSumClosest(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype int

    (Knowledge)

    思路：
    1. 首先对输入的数组进行排序；
    2. 接着固定一个数，对固定数右侧的剩余数组使用双指针进行遍历，期间考虑数组有序通过移动指针逼近target；
    3. 同时对已经遍历过的相同数字进行跳过，达到剪枝的目的

    PS: 本解法性能更优，耗时68ms左右，只要理解如何利用双指针逼近target即可：
        此处有图解 => https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/
    """
    # 先对数组进行排序
    nums, result, miniGap = sorted(nums), nums[0] + nums[1] + nums[2], abs(target - (nums[0] + nums[1] + nums[2]))

    # 先令first为比第一个值还小的一个值，由于上面执行了排序
    # 所以此时数组中所有的元素都不会等于这个数（第一轮判断的时候就肯定不会跳过）
    first = nums[0] - 1

    # 长度为n的数组，只需要遍历前n-2个数字即可，后面只有两个或者一个数字是无法构成结果要求的三个数字的
    for i in range(len(nums) - 2):

        # 遇到相同的直接跳过（因为每一轮固定一个值，就相当于第一个数为固定值的所有符合条件的三元组都已经添加了）
        if nums[i] == first:
            continue

        # 取当值作为固定值
        first = nums[i]
        left, right = i + 1, len(nums) - 1
        while left < right:
            tmp = first + nums[left] + nums[right]
            if abs(target - tmp) < miniGap:
                result, miniGap = tmp, abs(target - tmp)
            if tmp < target:
                left += 1
            elif tmp > target:
                right -= 1
            else:
                return tmp
    return result

测试验证

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype int

        (Knowledge)

        思路：
        1. 首先对输入的数组进行排序；
        2. 接着固定一个数，对固定数右侧的剩余数组使用双指针进行遍历，期间考虑数组有序通过移动指针逼近target；
        3. 同时对已经遍历过的相同数字进行跳过，达到剪枝的目的

        PS: 本解法性能更优，耗时68ms左右，只要理解如何利用双指针逼近target即可：
            此处有图解 => https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/
        """
        # 先对数组进行排序
        nums, result, miniGap = sorted(nums), nums[0] + nums[1] + nums[2], abs(target - (nums[0] + nums[1] + nums[2]))

        # 先令first为比第一个值还小的一个值，由于上面执行了排序
        # 所以此时数组中所有的元素都不会等于这个数（第一轮判断的时候就肯定不会跳过）
        first = nums[0] - 1

        # 长度为n的数组，只需要遍历前n-2个数字即可，后面只有两个或者一个数字是无法构成结果要求的三个数字的
        for i in range(len(nums) - 2):

            # 遇到相同的直接跳过（因为每一轮固定一个值，就相当于第一个数为固定值的所有符合条件的三元组都已经添加了）
            if nums[i] == first:
                continue

            # 取当值作为固定值
            first = nums[i]
            left, right = i + 1, len(nums) - 1
            while left < right:
                tmp = first + nums[left] + nums[right]
                if abs(target - tmp) < miniGap:
                    result, miniGap = tmp, abs(target - tmp)
                if tmp < target:
                    left += 1
                elif tmp > target:
                    right -= 1
                else:
                    return tmp
        return result


if __name__ == '__main__':
    solution = Solution()
    print(solution.threeSumClosest([-3, -2, -5, 3, -4], -1), "= -2")
    print(solution.threeSumClosest([0, 1, 2], 0), "= 3")
    print(solution.threeSumClosest([1, 1, 1, 1], 0), "= 3")
    print(solution.threeSumClosest([-1, 2, 1, -4], 1), "= 2")