algorithm - 最后 k 位的总和与前 k 位的总和相同

Question

我想找出给定范围内少数数字的前 k 位数字的总和是否等于最后 k 位数字的总和。这里的范围很大，k 小于 20。

我们可以做到这一点的一种方法是蛮力方法。有人可以建议一些其他有效的算法。同样的？

Answer 1

如果是一个范围，则第一个数字不会经常变化，最后一个数字会以简单的方式变化。S 是前 20 位数字的总和。虽然第二位不变，但当您转到下一位时，总和将加一。因此，如果除最后一位之外的所有数字都是固定的，并且如果最后一位数字等于 i 的总和是 Si，那么您唯一好的最后一位数字是 n= S - Si + i。然后，您必须检查 n 是否介于 0 和 9 之间，以及结果数字是否在区间内。这将查找次数减少了 10 次。

您可以检查下一个第二个较低的数字。
如果第一个 n 小于 0，则需要将第二个数字减少 -n。调用 n2 这个第二个数字。如果 n2 > = 0，好的数字将以 (n2,0), (n2 -1,1), ..., (0, n2) 结尾。这会将复杂度降低 100。如果 n 大于 10，则将第二个数字增加 n-9。将 n2 称为第二个数字。如果 n2<=9，好的数字是 (n2,9),(n2-1,8),...,(0,something)。这也将复杂度降低了 100。

您可以对第三个数字执行相同的操作，然后对第四个数字执行相同的操作，直到 20。这将导致只有 1 个总和，以及 O（解决方案数）的复杂性，因此它是最小的。对于编码，请注意您的第一个数字可能会发生变化。每组 20 个第一个数字进行一次计算。

Answer 2

如果您要对同一个数组多次使用它，您可以将所有元素与前面的元素相加，这就是O(n)数组的大小，n即

for(int i = 1; i < n; i++)
     arr[i] = arr[i] + arr[i-1];

这会将您的数组从概率密度函数转换为累积分布函数（对于离散数字）。因此，您的查询将是O(1)ie

if(arr[k-1] == (arr[n-1]-arr[n-k])) //arr[k-1] is sum of first k element
    return true;
return false;

Answer 3

对蛮力的另一个改进：

i = 0, T = 0
while |T| < 9 * (k - i) 
  T = T + last[i] - first[i]
  i = i + 1
return T == 0 

Answer 4

蛮力法的一项理论改进：

1) 将前 k 位相加，存储在sumFirst
2) 将最后 k 位相加，但如果 sum 超过 则停止sumFirst。

第 2 点可以省去对最后几位数字的总结。

但是您必须衡量额外的逻辑是否比简单地添加所有 k 位成本更高。

Answer 5

优化 Nk

改进算法的一种方法是，如果具有 N 位数字的数字具有以下属性：
N < 2k.

例如，如果 N = 5 且 k = 3 5 < 2x3，则数字为

abcde

您只需计算ab（de即无需检查k（3）位数字，因为第 3 位^由k-last 和 k-first 数字共享）。
也就是说，两边要计算的位数只有

min(k, N-k), having N >= k