时间戳

首页 > 解决方案 > 找到总和为 N 的对的更好方法

python - 找到总和为 N 的对的更好方法

问题描述

有没有更快的方法来写这个，该函数需要一个列表和一个值来查找该列表中的数值对，它们总和为 N 而没有重复我试图通过使用集合而不是使用列表本身来使其更快（但是我使用了 count()，我知道它是线性时间）我知道的任何建议都可能有办法

def pairsum_n(list1, value):

    set1 = set(list1)
    solution = {(min(i, value - i) , max(i, value - i)) for i in set1 if value - i in set1}
    solution.remove((value/2,value/2)) if list1.count(value/2) < 2 else None           
    return solution
"""
    Example: value = 10, list1 = [1,2,3,4,5,6,7,8,9]
    pairsum_n = { (1,9), (2,8), (3,7), (4,6) }
    Example: value = 10,  list2 = [5,6,7,5,7,5,3]
    pairsum_n = { (5,5), (3,7) }
"""

标签： python

解决方案

试试这个，运行时间 O(nlogn)：

v = [1, 2, 3, 4, 5, 6, 7, 8, 9]
l = 0
r = len(v)-1

def myFunc(v, value):

    ans = []

    % this block search for the pair (value//2, value//2)
    if value % 2 == 0:
        c = [i for i in v if i == value // 2]
        if len(c) >= 2:
            ans.append((c[0], c[1]))

    v = list(set(v))
    l = 0
    r = len(v)-1
    v.sort()
    while l<len(v) and r >= 0 and l < r:
        if v[l] + v[r] == value:
            ans.append((v[l], v[r]))
            l += 1
            r -= 1
        elif v[l] + v[r] < value:
            l += 1
        else:
            r -= 1

    return list(set(ans))

它被称为Two pointers technique，它的工作原理如下。首先，对数组进行排序。这要求 O(nlogn) 的最小运行时间。然后设置两个指针，一个指向数组的开头，l另一个指向它的最后一个元素r（指针名称是左和右）。

现在，看看名单。如果在位置 l 和 r 返回的值的总和低于我们正在寻找的值，那么我们需要递增l。如果它更大，我们需要递减r。

如果v[l] + v[r] == value比我们可以增加/减少两者，l或者r因为在任何情况下我们都想跳过值的组合，(v[l], v[r])因为我们不想重复。

推荐阅读