检查数字不是列表中 2 个整数的总和
Check number not a sum of 2 ints on a list
给定一个整数列表,我想检查第二个列表并从第一个列表中删除那些可以不能由第二个数字的总和组成的列表。所以给定 a = [3,19,20]
和 b = [1,2,17]
,我想要 [3,19]
.
看起来像是有两个嵌套循环的小菜一碟 - 除了我被 break
和 continue
命令卡住了。
这是我拥有的:
def myFunction(list_a, list_b):
for i in list_a:
for a in list_b:
for b in list_b:
if a + b == i:
break
else:
continue
break
else:
continue
list_a.remove(i)
return list_a
我知道我需要做什么,只是语法似乎不必要地令人困惑。有人可以告诉我更简单的方法吗? TIA!
你可以这样做,
In [13]: from itertools import combinations
In [15]: [item for item in a if item in [sum(i) for i in combinations(b,2)]]
Out[15]: [3, 19]
combinations
会给出b
中所有可能的组合,得到求和列表。只需检查 a
中是否存在该值
编辑
如果你不想用itertools
写一个函数给它。像这样,
def comb(s):
for i, v1 in enumerate(s):
for j in range(i+1, len(s)):
yield [v1, s[j]]
result = [item for item in a if item in [sum(i) for i in comb(b)]]
代码评论:
- 在遍历列表时从列表中删除元素是非常危险的。也许您可以将要保留的项目附加到新列表中,然后 return。
- 您当前的算法是
O(nm^2)
,其中n
是list_a
的大小,m
是list_b
的大小。这是相当低效的,但这是解决问题的良好开端。
- 还有很多不必要的
continue
和 break
语句,这会导致难以调试的复杂代码。
- 你也把所有东西都放在了一个函数里。如果您将每个任务拆分为不同的功能,例如将一个功能专门用于查找对,另一个用于检查
list_a
中的每个项目与 list_b
。这是一种将问题拆分成更小的问题,并用它们来解决更大的问题的方法。
总的来说,我认为你的功能做得太多了,通过分解问题可以将逻辑压缩成更简单的代码。
另一种方法:
由于觉得这个任务很有趣,所以我决定亲自尝试一下。我概述的方法如下所示。
1. 您可以首先使用散列法在 O(n)
时间内检查列表是否具有一对给定的总和:
def check_pairs(lst, sums):
lookup = set()
for x in lst:
current = sums - x
if current in lookup:
return True
lookup.add(x)
return False
2. 然后你可以使用这个函数来检查 list_b
中的任何一对是否等于 list_a
中迭代的数字的总和:
def remove_first_sum(list_a, list_b):
new_list_a = []
for x in list_a:
check = check_pairs(list_b, x)
if check:
new_list_a.append(x)
return new_list_a
它保留 list_a
中的数字,这些数字构成 list_b
中两个数字的总和。
3.上面也可以用列表推导写成:
def remove_first_sum(list_a, list_b):
return [x for x in list_a if check_pairs(list_b, x)]
两者的工作原理如下:
>>> remove_first_sum([3,19,20], [1,2,17])
[3, 19]
>>> remove_first_sum([3,19,20,18], [1,2,17])
[3, 19, 18]
>>> remove_first_sum([1,2,5,6],[2,3,4])
[5, 6]
注意:总体上上面的算法是O(n)
时间复杂度,不需要太复杂的东西。但是,这也导致了O(n)
额外的辅助space,因为要保留一个set来记录看过哪些item。
您可以先创建所有可能的总和组合,然后过滤掉不属于该组合列表的元素
定义输入列表
>>> a = [3,19,20]
>>> b = [1,2,17]
接下来我们将定义两个元素之和的所有可能组合
>>> y = [i+j for k,j in enumerate(b) for i in b[k+1:]]
接下来我们将对列表 a
的每个元素应用一个函数,并检查它是否存在于上面计算的列表中。 map
函数可以与 if/else
子句一起使用。如果 else 子句成功,map
将产生 None
。为了满足这一点,我们可以过滤列表以删除 None
值
>>> list(filter(None, map(lambda x: x if x in y else None,a)))
以上操作会输出:
>>> [3,19]
你也可以将所有这些行组合成一行来写一行,但我不推荐这样做。
你可以尝试类似的方法:
a = [3,19,20]
b= [1,2,17,5]
n_m_s=[]
data=[n_m_s.append(i+j) for i in b for j in b if i+j in a]
print(set(n_m_s))
print("after remove")
final_data=[]
for j,i in enumerate(a):
if i not in n_m_s:
final_data.append(i)
print(final_data)
输出:
{19, 3}
after remove
[20]
给定一个整数列表,我想检查第二个列表并从第一个列表中删除那些可以不能由第二个数字的总和组成的列表。所以给定 a = [3,19,20]
和 b = [1,2,17]
,我想要 [3,19]
.
看起来像是有两个嵌套循环的小菜一碟 - 除了我被 break
和 continue
命令卡住了。
这是我拥有的:
def myFunction(list_a, list_b):
for i in list_a:
for a in list_b:
for b in list_b:
if a + b == i:
break
else:
continue
break
else:
continue
list_a.remove(i)
return list_a
我知道我需要做什么,只是语法似乎不必要地令人困惑。有人可以告诉我更简单的方法吗? TIA!
你可以这样做,
In [13]: from itertools import combinations
In [15]: [item for item in a if item in [sum(i) for i in combinations(b,2)]]
Out[15]: [3, 19]
combinations
会给出b
中所有可能的组合,得到求和列表。只需检查 a
编辑
如果你不想用itertools
写一个函数给它。像这样,
def comb(s):
for i, v1 in enumerate(s):
for j in range(i+1, len(s)):
yield [v1, s[j]]
result = [item for item in a if item in [sum(i) for i in comb(b)]]
代码评论:
- 在遍历列表时从列表中删除元素是非常危险的。也许您可以将要保留的项目附加到新列表中,然后 return。
- 您当前的算法是
O(nm^2)
,其中n
是list_a
的大小,m
是list_b
的大小。这是相当低效的,但这是解决问题的良好开端。 - 还有很多不必要的
continue
和break
语句,这会导致难以调试的复杂代码。 - 你也把所有东西都放在了一个函数里。如果您将每个任务拆分为不同的功能,例如将一个功能专门用于查找对,另一个用于检查
list_a
中的每个项目与list_b
。这是一种将问题拆分成更小的问题,并用它们来解决更大的问题的方法。
总的来说,我认为你的功能做得太多了,通过分解问题可以将逻辑压缩成更简单的代码。
另一种方法:
由于觉得这个任务很有趣,所以我决定亲自尝试一下。我概述的方法如下所示。
1. 您可以首先使用散列法在 O(n)
时间内检查列表是否具有一对给定的总和:
def check_pairs(lst, sums):
lookup = set()
for x in lst:
current = sums - x
if current in lookup:
return True
lookup.add(x)
return False
2. 然后你可以使用这个函数来检查 list_b
中的任何一对是否等于 list_a
中迭代的数字的总和:
def remove_first_sum(list_a, list_b):
new_list_a = []
for x in list_a:
check = check_pairs(list_b, x)
if check:
new_list_a.append(x)
return new_list_a
它保留 list_a
中的数字,这些数字构成 list_b
中两个数字的总和。
3.上面也可以用列表推导写成:
def remove_first_sum(list_a, list_b):
return [x for x in list_a if check_pairs(list_b, x)]
两者的工作原理如下:
>>> remove_first_sum([3,19,20], [1,2,17])
[3, 19]
>>> remove_first_sum([3,19,20,18], [1,2,17])
[3, 19, 18]
>>> remove_first_sum([1,2,5,6],[2,3,4])
[5, 6]
注意:总体上上面的算法是O(n)
时间复杂度,不需要太复杂的东西。但是,这也导致了O(n)
额外的辅助space,因为要保留一个set来记录看过哪些item。
您可以先创建所有可能的总和组合,然后过滤掉不属于该组合列表的元素
定义输入列表
>>> a = [3,19,20]
>>> b = [1,2,17]
接下来我们将定义两个元素之和的所有可能组合
>>> y = [i+j for k,j in enumerate(b) for i in b[k+1:]]
接下来我们将对列表 a
的每个元素应用一个函数,并检查它是否存在于上面计算的列表中。 map
函数可以与 if/else
子句一起使用。如果 else 子句成功,map
将产生 None
。为了满足这一点,我们可以过滤列表以删除 None
值
>>> list(filter(None, map(lambda x: x if x in y else None,a)))
以上操作会输出:
>>> [3,19]
你也可以将所有这些行组合成一行来写一行,但我不推荐这样做。
你可以尝试类似的方法:
a = [3,19,20]
b= [1,2,17,5]
n_m_s=[]
data=[n_m_s.append(i+j) for i in b for j in b if i+j in a]
print(set(n_m_s))
print("after remove")
final_data=[]
for j,i in enumerate(a):
if i not in n_m_s:
final_data.append(i)
print(final_data)
输出:
{19, 3}
after remove
[20]