优化算法以查找满足特定属性的六位数字的数量

Question

问题:"一种算法,用于查找六位数字的数字,其中前三位数的总和等于最后三位数的总和."

我在一次采访中遇到了这个问题,想知道最好的解决方案.这就是我现在所拥有的.

方法1:当然,蛮力解决方案是检查每个数字(在100,000和999,999之间)的前三位和后三位的总和是否相等.如果是,则递增某个计数器,该计数器保持所有这些数字的计数.

但这会检查所有900,000个数字,因此效率低下.

方法2:由于我们被问到"有多少"这样的数字而不是"哪个数字",我们可以做得更好.将数字分为两部分:前三个数字(从100到999)和后三个数字(从000到999).因此,候选数字的任一部分中的三个数字的总和可以在1到27的范围内.
*std::map<int, int>对于每个部分保持a ,其中key是和,并且值是在相应部分中具有该总和的数字(3位数).
*现在,对于第一部分中的每个数字,找出它的总和并更新相应的地图.
*同样,我们可以获得第二部分的更新地图.*现在通过乘以相应的对(例如,键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.