算法面试真题详解:最接近的三数之和-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

算法面试真题详解:最接近的三数之和

简介: 算法面试真题详解:最接近的三数之和

描述
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组,返回这三个数的和。
只需要返回三元组之和,无需返回三元组本身

在线评测地址:领扣题库官网

样例1
输入:[2,7,11,15],3
输出:20
解释:
2+7+11=20
样例2
输入:[-1,2,1,-4],1
输出:2
解释:
-1+2+1=2

解法思路

  • 本题是57. 三数之和的扩展问题,不再要求恰好相等,而是找与target最接近的三数之和。
  • 本题需要计算三数之和,如果用暴力枚举,时间复杂度会是O(n3)O(n3)。我们这里采用双指针的方法,来降低时间复杂度。首先将数组排序,然后固定一个数numbersi上用双指针来找与target最接近的三数之和nearest。
    算法流程
  • 第一步,对数组进行排序。只有将数组转化为有序数组,我们才方便移动双指针。
  • 第二步,在数组numbers中遍历,每次固定numbers[i]作为第一个数
    • 建立双指针left和right,初始化分别指向i + 1和len(numbers) - 1
  • 求出此时的三数之和curr,如果curr和target恰好相等,我们可以直接返回target。
  • 比较curr和nearest谁距离target更近,如果是curr,那么将nearest更新为target
  • 判断curr和target的大小关系,如果curr > target,那么right左移;反之,left右移。继续第二步的过程,直到left >= right。
  • 此外,当数组中有重复元素时,为了避免重复运算,在代码中添加了三处剪枝操作。当指针指向新的位置和旧的位置的值相等时,我们继续移动指针。
    算法复杂度
  • 时间复杂度
    • 数组排序的时间复杂度为O(nlogn)O(nlogn)
  • 遍历过程,固定值为 n 次,双指针为 n 次,时间复杂度为 O(n2))O(n2))
  • 总时间复杂度:O(nlogn)+O(n2)=O(n2)O(nlogn)+O(n2)=O(n2)
  • 空间复杂度为O(1),只需要常量空间。
    class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @param target: An integer
    @return: return the sum of the three integers, the sum closest target.
    """
    def threeSumClosest(self, numbers, target):
        nearest = float('inf')
        # step1: 首先对数组进行排序
        numbers = sorted(numbers)
        # step2: 遍历
        for i in range(len(numbers) - 2):
            # 剪枝1
            if (i > 0 and numbers[i] == numbers[i - 1]):
                continue
            # 定义双指针
            left = i + 1
            right = len(numbers) - 1
            # 双指针相向而行
            while (left < right):
                # 此时的三数之和
                curr = numbers[left] + numbers[right] + numbers[i]
                # 和恰好为target
                if curr == target:
                    return target
                # 更新 nearest
                if abs(curr - target) < abs(nearest - target):
                    nearest = curr
                # 移动双指针
                if curr > target:
                    right -= 1
                    # 剪枝2
                    while (right >= 0 and numbers[right] == numbers[right + 1]):
                        right -= 1
                else:
                    left += 1
                    # 剪枝3
                    while (left < len(numbers) and numbers[left] == numbers[left - 1]):
                        left += 1
        return nearest

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接