时间戳

首页 > 解决方案 > Code Fight findClosestPair没有返回总和之间的正确距离

python - Code Fight findClosestPair没有返回总和之间的正确距离

问题描述

我正在尝试解决代码冲突并让一切正常，除了以下测试用例：

Input:
numbers: [1, 0, 2, 4, 3, 0]
sum: 5
Output:
Run the code to see output
Expected Output:
2
Console Output:
Empty

代码战的目标是： 给定一个整数数组，我们希望找到相加为和的最接近的元素对。返回最近对之间的距离（两个索引之间的绝对差异）。如果没有一对相加为和，则返回 -1。示例 对于 numbers = [1, 0, 2, 4, 3, 0] 和 sum = 5，输出应为 findClosestPair(numbers, sum) = 2。1 和 4 的和为 5，但 2 和 3 更接近。对于 numbers = [2, 3, 7] 和 sum = 8，输出应该是 findClosestPair(numbers, sum) = -1。没有总和为 8 的对。

以下函数将为所有情况返回所有数字，但后续数字集更接近。在上面的示例中，2 和 3 更接近，应该返回 2 的距离，但我的代码拾取 1 和 4 并停止并返回它。如何修复它以添加 if 语句以允许返回更小的距离？

def findClosestPair(numbers, sum):
    num_len = len(numbers)
    distance = 10
    for x in range(num_len):
        for y in range(x+1,num_len):
            if numbers[x] + numbers[y] == sum:
                if distance > abs(y-x):
                    distance = abs(y-x)
            else:
                continue
            return distance
    else:
        return int(-1)

此代码运行但需要很长时间才能运行。

def findClosestPair(numbers, sum):
    num_len = len(numbers)
    distance = 10
    for x in range(num_len):
        for y in range(x+1,num_len):
            if numbers[x] + numbers[y] == sum:
                if distance > abs(y-x):
                    distance = abs(y-x)
    if distance != 10:
        return distance
    else:
        return int(-1)

标签： pythonfor-loopif-statement

解决方案

那return distance是放错地方了，一旦发现任何低于当前最小距离的条目，您就会返回部分结果。

任何长度的数组的正确代码，与您的第二个片段非常相似：

#!/usr/bin/python3

def findClosestPair(numbers, sum):
    num_len = len(numbers)
    distance = num_len + 1
    for x in range(num_len):
        for y in range(x+1,num_len):
            if numbers[x] + numbers[y] == sum:
                if distance > abs(y-x):
                    distance = abs(y-x)
    if distance > num_len:
        return int(-1)
    else:
        return distance

n = [ 1, 0, 2 , 4 ,3, 0]

x = findClosestPair(n,5)

print(x)

只有当 时，您才能从循环中提前返回distance == 1，因为您知道您将无法找到比这更接近的任何对。

一种更快的方法是按升序检查每个距离，因此只要找到匹配的总和就可以立即返回：

def findClosestPair2(numbers, sum):
    num_len = len(numbers)
    for distance in range(1,num_len-1):
        for x in range(0,num_len-distance):
            if numbers[x] + numbers[x+distance] == sum:
                return distance
    return int(-1)

推荐阅读