这个算法有O（N）解吗？

Question

包括重复项和倒序对，它们相加为和

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9]

match = []
for i in range(len(numbers)):
    for j in range(len(numbers)):
        if (i!=j):
            if(numbers[i] + numbers[j] == sum):
                match.append([numbers[i], numbers[j]])

我需要检查匹配项和重复项，因此输出需要看起来像[[1, 9], [2, 8], [2, 8], [2, 8], [5, 5], [5, 5], [5, 5], [5, 5], [5, 5], [5, 5], [8, 2], [8, 2], [8, 2], [9, 1]]

Answer 1

正如评论中提到的，一般情况下没有O(n)的解决方案，因为在最坏的情况下，您需要输出n^2对数字，这显然不能在O(n)时间内完成。但是对于数组中没有等号的情况有线性解，只需使用字典：

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9]
tgr = 10

num2idx = {numbers[i]: i for i in xrange(len(numbers))}
for i in xrange(len(numbers)):
    x = numbers[i]
    y = trg - x
    if y in num2idx:
        j = num2idx[y]
        while j >= 0 and numbers[j] == y:
            if i != j:
                print x, y
            j -= 1

Answer 2

In[50]: numbers
Out[50]: [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9]
In[51]: expected_result
Out[51]: 
[[1, 9],
 [2, 8],
 [2, 8],
 [2, 8],
 [5, 5],
 [5, 5],
 [5, 5],
 [5, 5],
 [5, 5],
 [5, 5],
 [8, 2],
 [8, 2],
 [8, 2],
 [9, 1]]
In[52]: from collections import Counter
   ...: 
   ...: 
   ...: def matches(nums, target):
   ...:     cnt = Counter(nums)
   ...:     result = []
   ...:     for num in nums:
   ...:         diff = target - num
   ...:         result.extend([[num, diff]] * (cnt[diff] - (diff == num)))
   ...:     return result
   ...: 
In[53]: matches(numbers, target=10) == expected_result
Out[53]: True

Answer 3

这是一个变体：

from collections import Counter


def sum_target(lst, target):

    unique_list = list(set(lst))
    counts = Counter(lst)

    remainders = {number: target-number for number in unique_list}

    match = set()
    for a, b in remainders.items():
        if b in remainders:
            match.add(tuple(sorted((a, b))))

    # restore multiplicities:
    ret = []
    for a, b in match:
        if a != b:
            mult = counts[a] * counts[b]
            ret.extend([a, b] for _ in range(mult))
            ret.extend([b, a] for _ in range(mult))
            # ret.append((mult, (a, b)))
            # ret.append((mult, (b, a)))
        else:
            mult = counts[a] * (counts[a]-1)
            ret.extend([a, a] for _ in range(mult))
            # if mult != 0:
                # ret.append((mult, (a, b)))

    return ret

不完全确定多重性是以你想要的方式处理的（在你的例子中，它们是我得到的两倍。。。为什么[5, 5]有6个版本？在原始列表中有三个5，你只能得到3对…）

---

如果列表中有许多重复项，那么根据输出的长度，我建议将代码的最后一部分更改为

^{pr2}$

得到结果

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9]
s = 10
print(sum_target(lst=numbers, target=s))
# [(3, (8, 2)), (3, (2, 8)), (6, (5, 5)), (1, (1, 9)), (1, (9, 1))]