Python 查找列表中哪个数字和某个数字相加的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3420937/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to find which number in a list sum up to a certain number
提问by avacariu
I have a list of numbers. I also have a certain sum. The sum is made from a few numbers from my list (I may/may not know how many numbers it's made from). Is there a fast algorithm to get a list of possible numbers? Written in Python would be great, but pseudo-code's good too. (I can't yet read anything other than Python :P )
我有一个数字列表。我也有一定的数目。总和是由我列表中的几个数字组成的（我可能/可能不知道它是由多少个数字组成的）。是否有一种快速算法来获取可能的数字列表？用 Python 编写会很棒，但伪代码也很好。（除了 Python 之外，我还不能阅读任何其他内容：P）
Example
例子
list = [1,2,3,10]
sum = 12
result = [2,10]
NOTE:I do know of Algorithm to find which numbers from a list of size n sum to another number(but I cannot read C# and I'm unable to check if it works for my needs. I'm on Linux and I tried using Mono but I get errors and I can't figure out how to work C# :(
ANDI do know of algorithm to sum up a list of numbers for all combinations(but it seems to be fairly inefficient. I don't need all combinations.)
注意：我确实知道算法可以从大小为 n 的列表中找到哪些数字与另一个数字相加（但我无法阅读 C#，也无法检查它是否适合我的需要。我在 Linux 上，我尝试使用单声道，但我得到的错误，我无法弄清楚如何工作的C＃:(
和我知道的算法来总结号码列表中的所有组合（但它似乎是相当低效的。我并不需要所有的组合.)
采纳答案by jbernadas
This problem reduces to the 0-1 Knapsack Problem, where you are trying to find a set with an exact sum. The solution depends on the constraints, in the general case this problem is NP-Complete.
这个问题简化为0-1 Knapsack Problem，你试图找到一个具有精确总和的集合。解决方案取决于约束，在一般情况下，这个问题是 NP-Complete。
However, if the maximum search sum (let's call it S) is not too high, then you can solve the problem using dynamic programming. I will explain it using a recursive function and memoization, which is easier to understand than a bottom-up approach.
但是，如果最大搜索和（我们称之为S）不是太高，那么您可以使用动态规划解决问题。我将使用递归函数和memoization来解释它，这比自底向上的方法更容易理解。
Let's code a function f(v, i, S), such that it returns the number of subsets in v[i:]that sums exactly to S. To solve it recursively, first we have to analyze the base (i.e.: v[i:]is empty):
让我们编写一个函数f(v, i, S)，以便它返回v[i:]总和为 的子集数S。要递归求解，首先我们要分析基数（即：v[i:]为空）：
S == 0: The only subset of
[]has sum 0, so it is a valid subset. Because of this, the function should return 1.S != 0: As the only subset of
[]has sum 0, there is not a valid subset. Because of this, the function should return 0.
S == 0： 的唯一子集
[]总和为 0，因此它是有效子集。因此，该函数应返回 1。S != 0：由于 的唯一子集
[]总和为 0，因此不存在有效子集。因此，该函数应返回 0。
Then, let's analyze the recursive case (i.e.: v[i:]is not empty). There are two choices: include the number v[i]in the current subset, or not include it. If we include v[i], then we are looking subsets that have sum S - v[i], otherwise, we are still looking for subsets with sum S. The function fmight be implemented in the following way:
然后，让我们分析递归情况（即：v[i:]不为空）。有两种选择：包括v[i]当前子集中的数字，或者不包括它。如果我们包含v[i]，那么我们正在寻找具有 sum 的子集S - v[i]，否则，我们仍在寻找具有 sum 的子集S。该功能f可以通过以下方式实现：
def f(v, i, S):
if i >= len(v): return 1 if S == 0 else 0
count = f(v, i + 1, S)
count += f(v, i + 1, S - v[i])
return count
v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))
By checking f(v, 0, S) > 0, you can know if there is a solution to your problem. However, this code is too slow, each recursive call spawns two new calls, which leads to an O(2^n) algorithm. Now, we can apply memoizationto make it run in time O(n*S), which is faster if Sis not too big:
通过检查f(v, 0, S) > 0，您可以知道您的问题是否有解决方案。但是，这段代码太慢了，每次递归调用都会产生两个新调用，从而导致 O(2^n) 算法。现在，我们可以应用memoization使其在 O(n*S) 时间内运行，如果S不是太大，它会更快：
def f(v, i, S, memo):
if i >= len(v): return 1 if S == 0 else 0
if (i, S) not in memo: # <-- Check if value has not been calculated.
count = f(v, i + 1, S, memo)
count += f(v, i + 1, S - v[i], memo)
memo[(i, S)] = count # <-- Memoize calculated result.
return memo[(i, S)] # <-- Return memoized value.
v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))
Now, it is possible to code a function gthat returns one subset that sums S. To do this, it is enough to add elements only if there is at least one solution including them:
现在，可以编写一个函数g来返回求和的一个子集S。为此，仅当存在至少一种包含元素的解决方案时添加元素就足够了：
def f(v, i, S, memo):
# ... same as before ...
def g(v, S, memo):
subset = []
for i, x in enumerate(v):
# Check if there is still a solution if we include v[i]
if f(v, i + 1, S - x, memo) > 0:
subset.append(x)
S -= x
return subset
v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))
Disclaimer: This solution says there are two subsets of [10, 10] that sums 10. This is because it assumes that the first ten is different to the second ten. The algorithm can be fixed to assume that both tens are equal (and thus answer one), but that is a bit more complicated.
免责声明：此解决方案表示 [10, 10] 有两个总和为 10 的子集。这是因为它假设前十个与后十个不同。该算法可以固定为假设两个十位相等（因此回答一个），但这有点复杂。
回答by 1arpit1
So, the logic is to reverse sort the numbers,and suppose the list of numbers is land sum to be formed is s.
所以，逻辑是对数字进行反向排序，假设数字列表是l并且要形成的总和是s。
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
then, we go through this loop and a number is selected from lin order and let say it is i.
there are 2 possible cases either iis the part of sum or not.
So, we assume that iis part of solution and then the problem reduces to lbeing l[l.index(i+1):]and sbeing s-iso, if our function is a(l,s) then we call a(l[l.index(i+1):] ,s-i). and if iis not a part of sthen we have to form sfrom l[l.index(i+1):]list.
So it is similar in both the cases , only change is if i is part of s, then s=s-i and otherwise s=s only.
然后，我们遍历这个循环，并按顺序从l中选择一个数字，假设它是i。有两种可能的情况，要么i是 sum 的一部分，要么不是。因此，我们假设我是解决方案的一部分，然后将问题简化为升福祉l[l.index(i+1):]和S ^是SI所以，如果我们的功能是（L，S）则称a(l[l.index(i+1):] ,s-i)。如果i不是s的一部分，那么我们必须从列表中形成sl[l.index(i+1):]。所以在这两种情况下都是相似的，唯一的变化是如果 i 是 s 的一部分，那么 s=si 否则只有 s=s 。
now to reduce the problem such that in case numbers in l are greater than s we remove them to reduce the complexity until l is empty and in that case the numbers which are selected are not a part of our solution and we return false.
现在为了减少问题，以便在 l 中的数字大于 s 的情况下，我们将它们删除以降低复杂性，直到 l 为空，在这种情况下，选择的数字不是我们解决方案的一部分，我们返回 false。
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
and in case l has only 1 element left then either it can be part of s then we return true or it is not then we return false and loop will go through other number.
如果 l 只剩下 1 个元素，那么它可以是 s 的一部分，然后我们返回 true 或者不是，那么我们返回 false 并且循环将通过其他数字。
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
note in the loop if have used b..but b is our list only.and i have rounded wherever it is possible, so that we should not get wrong answer due to floating point calculations in python.
请注意循环中是否使用了 b..但是 b 只是我们的列表。并且我尽可能地四舍五入，这样我们就不应该因为 Python 中的浮点计算而得到错误的答案。
r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
global r
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
if(a(sum_to_be_formed,list_of_numbers)):
print(r)
this solution works fast.more fast than one explained above. However this works for positive numbers only. However also it works good if there is a solution only otherwise it takes to much time to get out of loops.
这个解决方案工作得很快。比上面解释的要快。然而，这只适用于正数。然而，如果只有一个解决方案，它也能很好地工作，否则需要很长时间才能摆脱循环。
an example run is like this lets say
一个示例运行是这样的让我们说
l=[1,6,7,8,10]
and s=22 i.e. s=1+6+7+8
so it goes through like this
1.) [10, 8, 7, 6, 1] 22
i.e. 10 is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8 is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7 is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6 is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1
just to give a comparison which i ran on my computer which is not so good. using
只是为了比较我在我的电脑上运行的不太好。使用
l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
and
和
s=2000
s=2000
my loop ran 1018 times and 31 ms.
我的循环运行了 1018 次和 31 毫秒。
and previous code loop ran 3415587 times and took somewhere near 16 seconds.
之前的代码循环运行了 3415587 次，耗时接近 16 秒。
however in case a solution does not exist my code ran more than few minutes so i stopped it and previous code ran near around 17 ms only and previous code works with negative numbers also.
但是，如果解决方案不存在，我的代码运行了超过几分钟，所以我停止了它，以前的代码只运行了大约 17 毫秒，以前的代码也适用于负数。
so i thing some improvements can be done.
所以我认为可以做一些改进。
回答by unnobtainium
#!/usr/bin/python2
ylist = [1, 2, 3, 4, 5, 6, 7, 9, 2, 5, 3, -1]
print ylist
target = int(raw_input("enter the target number"))
for i in xrange(len(ylist)):
sno = target-ylist[i]
for j in xrange(i+1, len(ylist)):
if ylist[j] == sno:
print ylist[i], ylist[j]
This python code do what you asked, it will print the unique pair of numbers whose sum is equal to the target variable.
这个python代码按照你的要求执行，它将打印总和等于目标变量的唯一数字对。
if target number is 8, it will print: 1 7 2 6 3 5 3 5 5 3 6 2 9 -1 5 3
回答by cyz1996
I have found an answer which has run-time complexity O(n) and space complexity about O(2n), where n is the length of the list.
我找到了一个答案，它的运行时复杂度为 O(n)，空间复杂度为 O(2n)，其中 n 是列表的长度。
The answer satisfies the following constraints:
答案满足以下约束：
List can contain duplicates, e.g. [1,1,1,2,3] and you want to find pairs sum to 2
List can contain both positive and negative integers
列表可以包含重复项，例如 [1,1,1,2,3] 并且您想找到总和为 2 的对
列表可以包含正整数和负整数
The code is as below, and followed by the explanation:
代码如下，并附上说明：
def countPairs(k, a):
# List a, sum is k
temp = dict()
count = 0
for iter1 in a:
temp[iter1] = 0
temp[k-iter1] = 0
for iter2 in a:
temp[iter2] += 1
for iter3 in list(temp.keys()):
if iter3 == k / 2 and temp[iter3] > 1:
count += temp[iter3] * (temp[k-iter3] - 1) / 2
elif iter3 == k / 2 and temp[iter3] <= 1:
continue
else:
count += temp[iter3] * temp[k-iter3] / 2
return int(count)
- Create an empty dictionary, iterate through the list and put all the possible keys in the dict with initial value 0. Note that the key (k-iter1) is necessary to specify, e.g. if the list contains 1 but not contains 4, and the sum is 5. Then when we look at 1, we would like to find how many 4 do we have, but if 4 is not in the dict, then it will raise an error.
- Iterate through the list again, and count how many times that each integer occurs and store the results to the dict.
Iterate through through the dict, this time is to find how many pairs do we have. We need to consider 3 conditions:
3.1 The key is just half of the sum and this key occurs more than once in the list, e.g. list is [1,1,1], sum is 2. We treat this special condition as what the code does.
3.2 The key is just half of the sum and this key occurs only once in the list, we skip this condition.
3.3 For other cases that key is not half of the sum, just multiply the its value with another key's value where these two keys sum to the given value. E.g. If sum is 6, we multiply temp[1] and temp[5], temp[2] and temp[4], etc... (I didn't list cases where numbers are negative, but idea is the same.)
- 创建一个空字典，遍历列表并将所有可能的键放入字典中，初始值为 0。注意键 (k-iter1) 是必须指定的，例如如果列表包含 1 但不包含 4，并且sum 是 5。然后当我们查看 1 时，我们想找出我们有多少个 4，但是如果 4 不在 dict 中，那么它会引发错误。
- 再次遍历列表，并计算每个整数出现的次数并将结果存储到字典中。
遍历字典，这次是要找出我们有多少对。我们需要考虑3个条件：
3.1 键只是总和的一半，并且这个键在列表中出现了不止一次，例如列表是[1,1,1]，总和是2。我们把这个特殊情况当作代码所做的。
3.2 键只是总和的一半，并且这个键在列表中只出现一次，我们跳过这个条件。
3.3 对于其他键不是总和一半的情况，只需将其值与另一个键的值相乘，其中这两个键的总和为给定值。例如，如果 sum 为 6，我们将 temp[1] 和 temp[5]、temp[2] 和 temp[4] 相乘，等等......（我没有列出数字为负的情况，但想法是一样的。 )
The most complex step is step 3, which involves searching the dictionary, but as searching the dictionary is usually fast, nearly constant complexity. (Although worst case is O(n), but should not happen for integer keys.) Thus, with assuming the searching is constant complexity, the total complexity is O(n) as we only iterate the list many times separately.
最复杂的步骤是第 3 步，它涉及搜索字典，但由于搜索字典通常很快，复杂度几乎恒定。（虽然最坏的情况是 O(n)，但对于整数键不应该发生。）因此，假设搜索是常数复杂度，总复杂度是 O(n)，因为我们只分别迭代列表多次。
Advice for a better solution is welcomed :)
欢迎提供更好的解决方案的建议:)
