找到所有串联对之和的有效算法

Question

我参加了CodeSignal练习考试，并且能够通过14/16测试用例解决此问题。给您一个向量作为输入（整数列表），并且解决方案会很长很长。

[最初，我只是简单地使用了两个for循环的强力解决方案，并将当前a [i] concat a [j]添加到运行总计中。但是，我尝试通过使用记忆来优化此设置。我使用成对的unordered_map来检查是否已经计算了（i，j）对，如果是，则只返回缓存的结果。即使进行了优化，我仍然没有通过任何其他测试用例并获得14/16的结果。我缺少什么见解或优化？

我发现了类似的在线问题，但是他们的见识似乎不适用于此特定问题。

例如：Similar Problem

问题：

给出正整数的数组a，您的任务是计算每个可能的concat（a [i]，a [j]）的总和，其中concat（a [i]，a [j]）是a [I]和a的字符串表示形式的并置[j]分别。

Ex：

a = [10,2]
sol = 1344
a[0],a[0] = 1010
a[0],a[1] = 102
a[1],a[0] = 210
a[1],a[1] = 22
sum of above = 1344

Answer 1

让我们计算贡献a_i整数以在所有对中回答。有两种情况。数字a_i低的第一种情况。当总和为n * a_i时回答（n为整数整数）。第二种情况很重要。然后让我们以十进制表示法找到所有偏移量。用k_j表示整数整数长度j（以十进制表示的长度）。然后对所有值k_j * a_i * 10^j（j）的高部分加答案1 <= j <= 7。知道了k_j，我们就可以计算线性时间内所有数字a_i的答案。