如何优雅的解这个题？

[Gawain]

a=[1,2,3,4,5,6,7,8]

b=[1,2,3,4,5,6,7,8]

b=[1,2,3,4,5,6,7,8]

已知 a + b + c = 16

求全部 abc 的组合

线性代数还是数组啥的，都还给老师了，只会 for 循环了...

修正一下题目的说明，语文不好，引起歧义了。

假定有一串整数组成的数组，从中取出三个值，允许重复，三个值的和为一个特定值。

那么，这样的组合有哪些？


感谢回复中的各位大佬，这里我结合 7 楼和 14 楼给出的方案，写了个答案。

from itertools import combinations,combinations_with_replacement
import numpy as np


X=852
Y=[165,180,204,235,240,265,270,296,306,337,360,382,396,400]

def summation(data):
return np.sum(data) == X

res = list(filter(test, list(combinations_with_replacement(Y,3))))
print(res)

输出为[(235, 235, 382), (240, 306, 306)]
完美解决

res = list(filter(summation, list(combinations_with_replacement(Y,3))))

上文那句写错了，不是 test...

[Itoktsnhc]

呃 这是《三数之和》吗

[Itoktsnhc]

@Itoktsnhc
如果是三数之和, 一般是做好排序，在循环中固定其中一个值，然后左右两侧指针遍历才能保证单调性。

[fkdtz]

我先努力优雅的读懂这个题

[JasonLaw]

我不太理解“ 已知 a + b + c = 16”，a 、b 、c 不是数组吗？

[JasonLaw]

@fkdtz #3 me too

[singerll]

题干里面是等于还是属于。。。
如果是属于，b+c=16-a ，先列举 a 的值，再确定 b+c 的数组边界，然后在边界里面循环吧。比如 1+1+1 的组合，是不需要循环的。

[brucmao]

https://www.geeksforgeeks.org/python-three-element-sum-in-list/
这是不是你想要的

[lyang]

思考的时间，代码已经写完了，for 循环还好吧

[kiroter]

先遍历 a,b 相加得 ab, 在转 map ，遍历 c, key = 16-3, ab.get(key)

[kiroter]

key=16-c

[FYFX]

你给的这个例子就这个数据量为什么不循环，还是说这只是题目中的一个测试用例？

[BeautifulSoap]

9 楼思路对的，把 a 和 b 相加然后用 16 一个个去减，结果到 c 里找，存在的话就是对应的组合只需要 8x8+64 次计算，比穷举的 8x8x8 好

可问题在于上面说的，总共就这么小的数组，直接穷举也没问题

[Gawain]

@JasonLaw
@fkdtz
@singerll

我的错，应该 a b c 属于三个数组，是其中之一，相找这样的组合

[cccjh]

以前大学高数满分，现在只会普通思维了

https://gist.github.com/chen-jia-hao/94a1fbfecd402e838496a0331d65fa52

[Gawain]

@FYFX
@BeautifulSoap

实际问题虽然不是这么小的数组，但是也多大，确实可以循环穷举。

但是总觉得这样不够优雅

在想是不是有别的数学方法 比如用 nump 数组操作之类的 但是这方面的知识早就忘光了

总之，穷举完全没问题，就是抱着学习的态度，问问有没有别的方法

[Gawain]

@cccjh

非常感谢

[ji39]

能不能用心算

[wangyzj]

@cccjh #14 我就喜欢这样的直给

[wxf666]

这样？我没测试过


from bisect import bisect_left, bisect_right

a = set([1, 2, 3, 4, 5, 6, 7, 8])
b = sorted([1, 2, 3, 4, 5, 6, 7, 8])
c = set([1, 2, 3, 4, 5, 6, 7, 8])

for x in a:
　 for i in range(bisect_left(b, 16 - x - max(c)), bisect_right(b, 16 - x - min(c))):
　　 print(f'{x} + {b[i]} + {16 - x - b[i]} = 16')

[Jooooooooo]

你搜下 three sum leetcode.

这题当然暴力解是可以的, 不过有更好的方法.

[fkdtz]

three sum 乃至于 n sum 问题

[wangtian2020]

选择内存最小方案 ×
选择运行时间最短方案 ×
考虑到循环总次数尚可接受，选择不用动脑自己写的最快的 for 循环方案 √

[Gawain]

@brucmao
@Jooooooooo

非常感谢，这个貌似就是我要找到

[UIXX]

比较同意循环方案，省脑。

实际上，从几何的角度看，就是一个求平面上格点的问题。由于公式的特殊性（整个平面的倾斜角为 45 度），以及数值的特殊性（和为偶数），这些格点并不需要计算，可以被直接列出来。复杂度等同于输出规模。

和为奇数的情况也差不多。

如果公式变了（平面倾斜度不再是 45 度，甚至不再是平面），那代数法更好。

[akira]

@cccjh #14 楼 老凡尔赛。。 高数勉强及格的路过。。