目录

AaronJny

诗酒繁华,书剑天涯。

leetcode第16题 3Sum Closest(最接近的三数之和)

这道题也比较简单,只是在第 15 题上加了一些变化。题目的大概意思是说:

给定一个长度为 n 的整数数组 nums 和一个整数 target,需要你从数组中找出三个数字,这三个数字相加的和与 target 最接近,返回这三个数字的和。

样例输入:

nums = [-1,2,1,-4]
target = 1

样例输出:

2 (-1 + 2 + 1 = 2)

题目链接:https://leetcode.com/problems/3sum-closest/

相比较于第 15 题,大概有三个地方不同:

  1. 第 15 题里 target 固定为 0,这里的 target 是变化的
  2. 第 15 题里三个数相加必须等于 target,即假设三个数的和为 x,第 15 题要求 target-x==0,本题要求 abs(target-x)最小。
  3. 第 15 题要求返回所有满足条件的三个数的组合,而本题要求返回 abs(target-x)最小时的 x。

那么,可以借鉴第 15 题的思路,来解决这个问题。

解题思路:

  1. 首先,为数组排序。
  2. 实现一个二分查找算法,当查找成功时,返回给定值所在的坐标,不成功时,返回 left 的坐标。
  3. 同样的,我们枚举前两个数 a 和 b,然后在数组中二分查找(target-a-b),获得其坐标 pos。
  4. 注意,重点来了:不论二分查找是否成功(假设返回的坐标为 pos),在确定 a,b 的情况下,使得 abs(target-a-b-c)最小的 c 一定是(nums[pos-1],nums[pos],nums[pos+1])中的一个。之所以会这样,在于我们对二分查找算法的实现,如果不明白的话可以仔细想一下,应该没什么问题。然后我们对(nums[pos-1],nums[pos],nums[pos+1])三个数分别计算一下,就能找到确定 a,b 时,使得 abs(target-a-b-c)最小的 c 了。
  5. 我们枚举每一对 a,b,然后利用步骤 3,4 确定每一对 a,b 对应的 c,然后保留使得 abs(target-a-b-c)最小的 a,b,c 即可,最终返回 a+b+c 作为程序输出。
  6. 最终的时间复杂度约为 O(n^2logn)。

样例代码(python2):

class Solution(object):

    def bin_search(self, nums, key, left, right):
        """
        在nums[left:right+1]中查找key,
        当key存在nums中时,返回key的坐标;
        当key不存在时,返回迭代后的left坐标
        :param nums:
        :param key:
        :param left:
        :param right:
        :return:
        """
        while left <= right:
            mid = (left + right) >> 1
            if key == nums[mid]:
                return mid
            elif key < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return left

    def get_close_num(self, nums, pos, need_num, left_limit):
        """
        在nums[left_limit+1:]中,
        比较坐标pos和坐标 pos +1/-1(如果存在)对应的值和need_num的差值,
        找出最接近need_num的数并返回
        :param nums:
        :param pos:
        :param need_num:
        :param left_limit:
        :return:
        """
        # 超出范围
        if pos >= len(nums):
            pos -= 1
        # 默认nums[pos]与need_num最接近
        close_num = nums[pos]
        # 如果pos-1在范围内,比较nums[pos]和nums[pos-1]谁和need_num更接近
        if pos > left_limit + 1:
            if abs(need_num - nums[pos - 1]) < abs(need_num - close_num):
                close_num = nums[pos - 1]
        # 如果nums[pos+1]在范围内,就也比较nums[pos+1]
        if pos < len(nums) - 1:
            if abs(need_num - nums[pos + 1]) < abs(need_num - close_num):
                close_num = nums[pos + 1]
        # 返回最接近need_num的数
        return close_num

    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        # 排序,便于二分查找
        nums = sorted(nums)
        close_num = 0
        # 初始赋一个极大值
        close_dist = 1 << 30
        # 枚举前两个数
        for i in range(length - 2):
            for j in range(i + 1, length - 1):
                # 计算target-a-b
                tmp_sum_1 = nums[i] + nums[j]
                need_num = target - tmp_sum_1
                # 二分查找target-a-b
                pos = self.bin_search(nums, need_num, j + 1, length - 1)
                # 根据坐标找到使当前abs(target-a-b-c)最小的c
                tmp_close_num = self.get_close_num(nums, pos, need_num, j)
                tmp_sum = tmp_sum_1 + tmp_close_num
                tmp_close_dist = abs(target - tmp_sum)
                # 和全局最接近结果进行比较
                if tmp_close_dist < close_dist:
                    # 更接近则替换
                    close_num = tmp_sum
                    close_dist = tmp_close_dist
                # 当差值为0时,已经是最接近的结果了,就可以提前结束
                if close_dist == 0:
                    return target
        # 返回和target最接近的数
        return close_num

转载请注明出处:https://blog.csdn.net/aaronjny/article/details/88550964


标题:leetcode第16题 3Sum Closest(最接近的三数之和)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573017483100.html