c++ - 优化算法以找到满足特定属性的六位数字的数量

Question

问题:“一种算法，用于查找前三位数字之和等于后三位数字之和的六位数字的个数。”

我在面试中遇到了这个问题，想知道最好的解决方案。这是我到目前为止所拥有的。

方法 1:蛮力解决方案当然是检查每个数字(介于 100,000 和 999,999 之间)的前三位数字和后三位数字之和是否相等。如果是，则增加某个计数器，该计数器对所有此类数字进行计数。

但这会检查所有 900,000 个数字，因此效率很低。

方法 2:由于我们被问及“有多少”这样的数字而不是“哪些数字”，我们可以做得更好。将号码分成两部分:前三位数字(从 100 到 999)和最后三位数字(从 000 到 999)。因此，候选号码的任何一部分的三位数字之和可以介于 1 到 27 之间。
*维护std::map<int, int>对于每个部分，其中键是总和，值是相应部分中具有该总和的数字(3 位)的数量。
* 现在，对于第一部分中的每个数字，找出其总和并更新相应的 map 。
* 同样，我们可以获得第二部分的更新 map 。* 现在乘以相应的对(例如键 4 的映射 1 中的值和键 4 的映射 2 中的值)并将它们相加我们得到答案。

在这种方法中，我们最终检查了 1K 个数字。

我的问题是我们如何进一步优化？有更好的解决方案吗？

Answer 1

对于 0 <= s <= 18 , 正好有 10 - |s - 9|获取方式s作为两位数的总和。

所以，对于第一部分

int first[28] = {0};
for(int s = 0; s <= 18; ++s) {
    int c = 10 - (s < 9 ? (9 - s) : (s - 9));
    for(int d = 1; d <= 9; ++d) {
        first[s+d] += c;
    }
}

那是 19*9 = 171 次迭代，对于后半部分，做同样的事情，内部循环从 0 而不是 1 开始，那是 19*10 = 190 次迭代。然后求和 first[i]*second[i]对于 1 <= i <= 27 .