找出与给定数字N [duplicate]最接近的三个整数

This question already has an answer here:

这个问题已经有了答案:

Finding three elements in an array whose sum is closest to a given number 13 answers
在一个数组中找到三个元素，它们的和最接近给定的13个答案

after reading about Finding three elements in an array whose sum is closest to a given number, this is my attempt at implementing such algorithm

在阅读了关于查找数组中与给定数字最接近的三个元素之后，我尝试实现这种算法

def findThree(seq, goal):

    # initialize the differences 
    goalDifference = float("inf")
    dl = -1
    dr = -1
    dx = -1

    for x in range(len(seq)-1):

        left = x+1
        right = len(seq)-1


        while (left < right):

            # if the absolute value of the previous set and the goal is less than the current goalDifference,
            # keep track of the new set
            if(abs(goal - (seq[left] + seq[right] + seq[x])) < goalDifference):
                dl = left
                dr = right
                dx = x

            tmp = seq[left] + seq[right] + seq[x]

            if tmp > goal:
                right -= 1
            elif tmp < goal:
                left += 1
            else:
                return [seq[left],seq[right],seq[x]]

    # if no match is found, return the closest set
    return [seq[dl],seq[dr], seq[dx]]

The algorithm works great for finding exact solutions, given

该算法适用于寻找精确解。

arr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320]

findThree(arr, 349) // want to get [120, 140, 89]
>> [120, 140 89] // success

findThree(arr, 439) // want to get [140, 179, 120]
>> [140, 179,120] // success

however, when I want to see if it'll return the closest, it returns

但是，当我想知道它是否会返回最近的值时，它会返回

findThree(arr, 350) // only 1 more than 349, should return [120, 140, 89]
>> [320, 320, 259] // fail

findThree(arr, 440) // only 1 more than 439, should return [140, 179, 120]
>> [320, 320, 259] // fail

it appears that when I want it to return the "cloest" element, it always returns [320, 320, 259]. I've been looking at the code for a few hours now, but still can't figure out what's wrong.

当我希望它返回“cloest”元素时，它总是返回[320,320,259]。我已经看了几个小时的代码了，但还是不知道哪里出错了。

3 个解决方案

#1

I quickly looked through your code, the main problem is that the "goal difference" was never changed.

我很快看了你的代码，主要的问题是“目标差异”从来没有改变过。

You need to squeeze the "goal difference" as you go, otherwise all combinations are within the "goal difference", obviously you will end up having the last set as the answer.

你需要挤压“目标差异”，否则所有的组合都在“目标差”之内，显然你最终会得到最后一组答案。

#2

Actually, the problem here is that you are not keeping track of the closest combination of numbers. As per the current algorithm your code checks the combination till left = right-1 and x=left-1 (since left = x+1); . At the end of the execution of loop, you will have x=259, left=320 and right=320 always, if the correct combination is not achieved. thats why its returning the values of last iteration always i.e [320, 320, 259], when findThree(arr, 350) and findThree(arr, 440) were called. A solution may be to take three variable close1 close2 and close3 and initialize them to 0 before the start of for loop;and within for loop add following after the if statement:

实际上，这里的问题是，你没有跟踪最接近的数字组合。按照当前算法，代码检查组合，直到左=右1和x=左1(因为左= x+1);。在执行循环的最后，如果没有实现正确的组合，则x=259，左=320，右=320。这就是为什么它返回最后一次迭代的值总是i。e[320, 320, 259]，调用findThree(arr, 350)和findThree(arr, 440)。一个解决方案可能是在for循环开始之前取3个变量close1 close2和close3，并将它们初始化为0;

if(abs(goal - (seq[left] + seq[right] + seq[x])) < abs(goal - (close1 + close2 + close3)) ):
close1 = seq[left]
close2 = seq[right]
close3 = seq[x]

the above statements will check closest from the previous set and current set of left, right and x elements of array, and change the close1, close2 and close2 to current set of left, right and x if current combination is closer than the previous record of left, right and x which is stored in close1, close2 and close3 respectively.Otherwise close1, close2 and close3 shall not be changed. and at the end of code

上面的语句将检查最近从之前的设置和当前设置的左,右和x的元素数组,和改变close1 close2 close2当前设置的左,右和x如果目前的组合更比以前留下的记录,对存储在close1和x,分别close2和close3。否则，关闭1、关闭2和关闭3不能更改。在代码的最后

#if no match is found,return the closest set
return [close1 ,close2, close3]

#3

You could do something like:

你可以这样做:

def find3(tgt, arr):
    lowest=[float('inf')]
    for i in range(0,len(arr)-2):
        j=i+1
        k=len(arr)-1
        while k>=j:
            t=tuple(arr[x] for x in (i, j, k) )
            sum_t=sum(t)
            if sum_t==tgt:
                return t
            elif sum_t<sum(lowest):
                lowest=t     
            if sum_t>0:
                k-=1
            else:
                j+=1                    

    return lowest

Which works for all cases you describe.

它适用于你描述的所有情况。

#1