leetcode第16题 3Sum Closest（最接近的三数之和）

雨点打透心脏的1/2处 2022-03-08 05:10 198阅读 0赞

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

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

样例输入：

> nums = \[-1，2，1，-4\]  
> target = 1

样例输出：

> 2 `(-1 + 2 + 1 = 2)`

题目链接：[https://leetcode.com/problems/3sum-closest/][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][https_blog.csdn.net_aaronjny_article_details_88550964]

[https_leetcode.com_problems_3sum-closest]: https://leetcode.com/problems/3sum-closest/
[https_blog.csdn.net_aaronjny_article_details_88550964]: https://blog.csdn.net/aaronjny/article/details/88550964