修改后的 3SUM 算法不适用于浮点数

Question

所以我一直在尝试解决3SUM问题，下面是我的算法

def findThree(seq, goal):
    for x in range(len(seq)-1):
        left = x+1
        right = len(seq)-1
        while (left < right):
            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]]

正如你所看到的，这是一个非常通用的算法，它在O（n²）中求解。

我一直遇到的问题是，这种算法似乎不喜欢使用浮点数。

为了验证我的理论是正确的，我给了它下面的两个阵列

FloatingArr = [89.95, 120.0, 140.0, 179.95, 199.95, 259.95, 259.95, 259.95, 320.0, 320.0]
IntArr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320]

findThree(FloatingArr, 779.85) // I want it to return [259.95, 259.95, 259,95]
>> None // Fail
findThree(FloatingArr, 777) // I want it to return [259,259,259]
>> [259, 259, 259] // Success

该算法确实有效，但它似乎不能很好地处理浮点数。我能做些什么来解决这个问题？

为了获得更多信息，我的第一个数组最初是一串价格的列表，但为了计算它们，我不得不去掉"$"符号

for x in range(len(prices)):
    prices[x] = float(prices[x][1:]) // return all the prices without the "$" sign. Casting them to float. 

如果有更好的方法，请告诉我。我觉得这个问题不是关于findThree（），而是关于我如何修改原始价格数组。

编辑：鉴于这确实是一个浮点问题，我想我的下一个问题是，在去掉"$"后，将字符串转换为int的最佳方法是什么？

Answer 1

它不起作用，因为像89.95这样的数字通常无法准确存储（因为0.95的基二表示法是重复小数）。

一般来说，在处理浮点数时，您不需要通过==来比较精确的相等性，而是需要检查这些数字是否"足够接近"以被视为相等；通常用CCD_ 4来完成。SOME_THRESHOLD的确切值取决于您想要的准确度，通常需要反复尝试才能获得好的值。

在您的特定情况下，因为您使用的是美元和美分，您可以简单地通过乘以100并四舍五入为整数来转换为美分（通过round，因为int将把7.999999四舍五进为7）。然后，你的一组数字将只是整数，从而解决舍入问题。

Answer 2

您可以将价格从字符串转换为整数，而不是将其转换为浮点值。让我们假设所有价格的小数点后最多有k位（以初始字符串表示）。那么10^k * price总是一个整数。因此，您完全可以摆脱浮点计算。

示例：如果小数点后最多有两位数字，则$2.10变为210，$2.2变为220。即使在中间计算中也不需要使用float，因为您可以将小数点向右移动两个位置（必要时添加零），然后将字符串直接转换为整数。

以下是转换函数的示例：

def convert(price, max_digits):
    """ price - a string representation of the price
        max_digits - maximum number of digits after a decimal point
                     among all prices
    """
    parts = price[1:].split('.')
    if len(parts) == 2 and len(parts[1]) > 0:
        return int(parts[0]) * 10 ** max_digits + 
               int(parts[1]) * 10 ** (max_digits - len(parts[1]))
    else:
        return int(parts[0]) * 10 ** max_digits