找出所有满足 i+j+k=n 的三元组 i,j,k。

Question

我已经编写了这个代码，但它非常冗长：

for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i + j + k == n:

有没有一种聪明的方法使它运行更快？目前它是O(n^3)，这相当不理想。

- IHopeItWontBeAStupidQuestion

---

通过选择k=n-j-i并去掉最内层循环，可以轻松将此算法优化到O(n^2)。 - Nelewout

没有进一步的限制，有O(n^2)个可能的三元组可以加起来得到n，因此，不，你不能对最坏情况运行时间做太多事情。 - chepner

问题：对于 i != j，您需要同时返回 (i, j, k) 和 (j, i, k) 吗？ - Lukasz Wiecek

我认为O(n^2)已经是一个非常大的改进了。 - IHopeItWontBeAStupidQuestion

如果允许负值，则会有无限数量的三元组（例如，(n，j，-j)是任何j值的解），因此您不能指望明确找到它们所有。 - Stef

Answer 1

有几种可能的解决方法 - 实际上不需要在所有解决方法中循环到N，而最后一个数字是完全免费的。

请记住，三元组中的所有数字必须为正数（否则答案为无限大）。

1. If permutations are not included (i.e. (1,2,3) is the same triplet as (3,2,1)), going from smallest to largest:

   def iter_triplets(n):
       # This is the smallest number, can't be more than 1/3 of n
       for i in range(0, n//3 + 1):
           sum_left = n-i
           # This is the second smallest, can't be more than 1/2 of the sum_left or less than the first by definition
           for j in range(i, sum_left//2 + 1):
               yield (i, j, sum_left-j)  # Last number is calculated.
   
   
   >>> list(iter_triplets(6))  
   [(0, 0, 6), (0, 1, 5), (0, 2, 4), (0, 3, 3), (1, 1, 4), (1, 2, 3), (2, 2, 2)]
   >>> list(iter_triplets(10))
   [(0, 0, 10), (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6), (0, 5, 5), (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4), (3, 3, 4)]
   

2. If permutations are not included (i.e. (1,2,3) is the same triplet as (3,2,1)), going from largest to smallest:

   import math
   def iter_triplets(n):
       # This is the biggest number, can't be less than 1/3 of n
       for i in range(n, math.ceil(n/3) - 1, -1):
           sum_left = n-i
           # This is the second biggest number, can't be less than 1/2 of the sum_left and more than first number by definition.
           # ceil to correct rounding errors.
           for j in range(min(sum_left, i), math.ceil((sum_left)/2) - 1, -1):
               yield (i, j, sum_left-j)  # Last number is calculated.
   
   
   >>> list(iter_triplets(10))
   [(10, 0, 0), (9, 1, 0), (8, 2, 0), (8, 1, 1), (7, 3, 0), (7, 2, 1), (6, 4, 0), (6, 3, 1), (6, 2, 2), (5, 5, 0), (5, 4, 1), (5, 3, 2), (4, 4, 2), (4, 3, 3)]
   

3. If permutations are included (i.e. (1,2,3) is a different triplet than (3,2,1)), going from smallest to largest:

   def iter_triplet_permutations(n):
       for i in range(0, n+1):
           sum_left = n-i
           for j in range(0, sum_left+1):
               yield (i, j, sum_left-j)
   
   >>> list(iter_triplet_permutations(5)) 
   [(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1), (0, 5, 0), (1, 0, 4), (1, 1, 3), (1, 2, 2), (1, 3, 1), (1, 4, 0), (2, 0, 3), (2, 1, 2), (2, 2, 1), (2, 3, 0), (3, 0, 2), (3, 1, 1), (3, 2, 0), (4, 0, 1), (4, 1, 0), (5, 0, 0)]
   

- Bharel

---

是的，那就是正确的实现。 - Olvin Roght

Answer 2

由于一旦你有了i和j，最内层循环似乎是多余的，因为k是自带的：

for i in range(n + 1):
    for j in range(n + 1):
        if i+j <= n:
            print((i, j, n-i-j))

如果我们想要三个唯一数字的总和为n，那么也许可以这样做：

for i in range(n + 1):
    for j in range(i, (n - i)//2 + 1):
        out.append((i, j, n-i-j))

- user7864386

Answer 3

有几种方法可以让代码运行更快。

1. 使用列表推导式。语法为[条件 循环返回值]

2. 从上一个循环结束的地方开始下一个循环，以避免重复。

   def MakeTriplet(n):                                                                          
       return [(i,j,k) for i in range(0,n+1) for j in range(i,n+1) for k in range(j,n+1) if (i+j+k)==n]
   

- Francis King

---

我需要那些重复的数据。这就是关键。（抱歉在问题中没有提到） - IHopeItWontBeAStupidQuestion