首页 > 试题广场 >

最接近的三数之和

[编程题]最接近的三数之和

热度指数：12789 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出含有n个整数的数组s，找出s中和加起来的和最接近给定的目标值的三个整数。返回这三个整数的和。你可以假设每个输入都只有唯一解。

   例如，给定的整数 S = {-10 20 10 -40}, 目标值 = 10.
   最接近目标值的和为 2. (-10 + 20 + 10 = 20).

示例1

输入

[0,0,0],1

输出

算法知识视频讲解

Python

农夫三拳有点痒

violent solution（can not pass the test in regular time）

import sys
class Solution:
    def threeSumClosest(self , num , target ):
        # write code here
        n,temp,minus,res=len(num),0,sys.maxsize,0
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i!=j and j!=k and i!=k:
                        if abs(target-num[i]-num[j]-num[k])<=minus:
                            minus=abs(target-num[i]-num[j]-num[k])
                            res=num[i]+num[j]+num[k]
        return res

发表于 2020-06-21 16:56:21 回复(0)

Python

一直爬的蜗牛

# @param num int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def threeSumClosest(self , num , target ):
        # write code here
        if len(num) == 3:
            return num[0]+num[1]+num[2]
        
        num.sort()
        res = num[0]+num[1]+num[2]
        
        for i in range(len(num)):
            start = i+1
            end = len(num) - 1
            while start < end:
                cur_min = num[i] + num[start] + num[end]
                if cur_min == target:
                    return target
                if abs(cur_min - target) < abs(res - target):
                    res = cur_min
                if cur_min < target:
                    start += 1
                else:
                    end -= 1
        return res

发表于 2020-06-16 11:36:20 回复(0)

Python

牛客585071975号

有人可以帮我看一下哪里出错了吗，我实在找不出来了

#
# 
# @param num int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def threeSumClosest(self , num , target ):
        # write code here
        if len(num)>=3:
            num.sort()
            getsum=num[0]+num[1]+num[2]
        else:
            return 0
        for i in range(len(num)-2):
            
            j = i+1
            k = len(num)-1
            
            while(j<k):
                diff = (num[i]+num[j]+num[k]-target)
                j=j+1
                k=k-1
                if abs(diff) > abs(num[i]+num[j]+num[k]-target):
                    result = num[i]+num[j]+num[k]
                else:
                    result = diff+target
                diff = min(abs(num[i]+num[j]+num[k]-target),abs(diff))
        return result

发表于 2020-06-07 04:06:47 回复(0)