python - 一个循环？ Python

Question

所以我编写了这个给定可能数字的函数，它必须在可能数字中找到构成给定数字的两个数字。但是，我仍在学习 Python(一种非常棒的语言)，所以我只能使用有限的一组函数。

我创建了这个函数:

def sumPair(theList, n):

    theList = charCount(theList) #charCount is a function i made to convert the list into a dictionary
    for i in theList:
        for a,b in theList.iteritems():
            print a,b
            if a + i == n:
                if theList[b] > 1:
                    return [i, b]
                if a != i:
                    return [i, b]
        return "[]"
print sumPair([6,3,6,8,3,2,8,3,2], 11)   

就像我说的，它会找到加起来等于给定数字的两个数字。 charCount 是我编写的将数组添加到字典中的函数。

在这个程序中，我确保值大于 1，以防添加的数字相同。有时，如果它检查 10 的总和，而您给它一个数字 5，它只会将 5 添加到自身并返回 10。这就是 if theList[b] > 1: 的原因 在那里。

我为什么在这里？我的导师对两个循环不满意。我花了 5 个小时进行故障排除，但一无所获。我需要将这个程序转换成一个单循环程序。

我在这上面花了一整天，我不是要你做作业，我只是真的被困住了，我需要你的帮助。我听说我应该检查是否存在 key 才能完成此操作。

Answer 1

老师可能对您的算法花费的时间比实际需要的时间长不满意。试试这个:

for each element x in theList
  if there exists an element y in theList such that x+y = n, you have a match

您需要快速进行“if exists”测试，这正是您使用字典的目的。一个循环将建立这个字典，第二个将搜索。这将花费线性时间而不是您的 O(n^2) 时间。

你关于 5 与自身匹配的观点是一个很好的观点。您想要使用称为多重集或包的数据结构。阅读它然后以这种方式实现您的代码:

for each element x in theList
  if there exists an element y in theList such that x+y == n:
    if x != y or (x == y and x occurs more than once):
      you have a match

祝你好运。

编辑 因为有太多次优解，这里是简单的线性解(它是线性的，因为列表中有 2 个循环，但循环一个接一个地出现。所以，2 *n 次迭代，O(n)。非常快。

#!/usr/bin/python2.6

from collections import defaultdict

def sum_list(l, n):
  count = defaultdict(lambda: 0)

  for x in l:      # O(n)
    count[x] += 1  # This can be done in constant time O(1)

  for x in l:      # O(n)
    y = n - x
    if count[y] > 0 and (x != y or count[y] > 1): # O(1)
      return x, y