c++ - 更有效地找到所有具有相同总和的组合

Question

我想找到 -n 到 n 范围内的四个数字的所有组合，这些组合加起来为零。有没有有效的算法来解决这个问题？

#include <iostream>
using namespace std;

int main()
{
    int i, j, k, l;
    int size = 20;

    for (i = -size; i <= size; i++)
    {
        for (j = -size; j <= size; j++)
        {
            for (k = -size; k <= size; k++)
            {
                for (l = -size; l <= size; l++)
                {
                    if (i + j + k + l == 0)
                    {
                        cout << i << " " << j << " " << " " << k << " " << l << endl;
                    }
                }
            }

        }
    }
    return 0;

}

Answer 1

可能有很多方法可以优化这个算法，但这里有几个简单的方法。

首先，您根本不需要对数字进行最终循环:

for (l = -size; l <= size; l++)
    ...

这是因为现在已经定义了前三个数字，所以只有一个可能的数字可以使所有 4 个加起来为零。您所要做的就是找出该数字是多少，并检查它是否在 -n 到 +n 的范围内。

int l = 0 - (i+j+k);
if (-l >= -size && l <= size)
     ....

其次，在许多情况下第三个循环可以缩短，例如，如果 i 和 j 都是 -size，那么 k 的唯一可能值是 +size，它可以导致所有四个数字相加为零。使用这个想法，我们可以在这个循环上设置额外的界限，在相当多的情况下缩短它。

这两项优化应该会大大加快该算法的速度。