数字的子串之和

Question

如何找到数字的所有子串之和的最优解？

例如，Sum (123) = 1 + 2 + 3 + 12 + 23 + 123 = 164。

我认为时间复杂度是O(n^2)，因为

sum = 0
for i in number: // O(n)
    sum += startwith(i) // O(n)
return sum

有没有最优解？什么是最佳方法？

这里是我的解决方案，但时间复杂度为 O(n^2)：

public static int sumOfSubstring(int i) {
  int sum = 0;

  String s = Integer.toString(i);

  for (int j = 0, bound = s.length(); j < bound; j++) {
   for (int k = j; k < bound; k++) {
    String subString = s.subSequence(j, k + 1).toString();
    sum += Integer.valueOf(subString);
   }
  }

  return sum;
 }

- user467871

---

我认为你的意思是“子字符串”，而不是“子序列”。 - Mehrdad Afshari

你想考虑将 2+3 用于 1234 吗？ - codaddict

@codaddict 当然，那么1 + 2 + 3 + 4 + 12 + 23 + 34 + 123 + 234 + 1234 - user467871

观察：对于数字XY，您有11X + 2Y。 对于数字XYZ，您有111X + 22Y + 3Z。 对于WXYZ，您有1111W + 222X + 33Y + 4Z。这有助于您在O（n lg n）中找到解决方案吗？ - Gabe

@Gabe 很棒的方法！听起来像是一个“正确的答案”。 - user467871

hilal：好的，我发布了一个O(n)的C#解决方案，除了字符串函数外，应该也适用于Java。 - Gabe

Answer 1

观察到：

• 对于数字 XY，您有 11X + 2Y。
• 对于数字 XYZ，您有 111X + 22Y + 3Z。
• 对于数字 WXYZ，您有 1111W + 222X + 33Y + 4Z。

这是我的 C# 实现，但很容易移植到 Java：

static long SumSubtring(String s)
{
    long sum = 0, mult = 1;
    for (int i = s.Length; i > 0; i--, mult = mult * 10 + 1)
        sum += (s[i - 1] - '0') * mult * i;
    return sum;
}

请注意，它的时间复杂度实际上是O(n)。

- Gabe

---

嘿，我认为算法中有一些错误。因为对于123，您得到333+2222+11111，应该是33+222+1111。 - therealprashant

@therealprashant：我没有看到问题；SumSubstring("123") 对我来说返回的是164。 - Gabe

@madanram，请看下面我单独回答的详细解释。 - Kaushik Lele

非常好。但是，在这种方法中，对于有超过10位数字的数字该怎么办？ - Siva Tumma

Answer 2

给定长度为n的字符串，可能有N^2个不同的子串。然而，我们可以使用以下方程在线性时间内计算总和：

S= 其中S代表数字序列(s0, s1, s2, ... , sn)。

例如对于S=<1,2,3>，它返回111*1+22*2+3*3=164。

需要注意的是，如果我们预先计算N个10的幂或在循环中逐步计算，则运行时间是线性的。

- Eyal Schneider

---

看看@Gabe的方法。观察：对于数字XY，您有11X + 2Y。对于数字XYZ，您有111X + 22Y + 3Z。对于WXYZ，您有1111W + 222X + 33Y + 4Z。这有助于您在O（n lg n）中找到解决方案吗？简单的数学和简单的算法。 - user467871

@hilal：我的公式完全按照你描述的模式，以正式的方式进行。它还证明了可以在线性时间内完成。我把实现留给了其他人 :) - Eyal Schneider

Answer 3

正如 @Gabe 提供的，您可以这样做：

A0 = 1,
A1 = A0*10 + 1,
...
An-1 = An-2 * 10 + 1,

你可以在O(n)的时间内计算A0-An

a[0] = 1;
for (int i=1;i<n;i++)
 a[i] = a[i - 1] * 10 + 1;

现在计算 b[i]：

b[0] = a[0] * n
b[1] = a[1] * (n-1)
...

你可以在O(n)的时间内计算出所有的b[i]

现在伪代码如下：

for (int i=0;i<n;i++)
   sum += S[n-i - 1] * b[i]

- Saeed Amiri

Answer 4

所有上面的答案看起来都很好。我最近解决了一个类似的问题。上面介绍的公式效果很好，但是随着字符串长度的增加，计算变得困难，解决方案变得非常大。通常当字符串长度非常大时，你会被要求在对一个大数取模后给出答案，比如1000000007。所以现在你可以使用一点模算术（或者更具体地说模幂运算和乘法逆元）轻松地计算这些值。因此，针对大输入量进行修改后的新公式可以写成以下形式。 假设条件。

• Modular_exp()是计算a^b % c的函数
• 乘法逆元变量是9的乘法逆元，即111111112，可以使用相同的Modular_exp()函数找到，但是这里我只是硬编码了它。
• len是仅包含从'0'到'9'的字符的字符串的总长度;

以下是代码：

FOR(i, len) {
    coef = (( ( modular_exp(10, len - i, MOD) - 1) * multiinverse ) % MOD) * (i + 1) % MOD;
    res += ( coef * (s[i] - '0') ) % MOD;
}
printf("%lld\n", res % MOD );

就这样。

- user3744500

Answer 5

FWIW，对于N位数要相加的整数数量似乎是

N + N-1 + N-2 ... 1

这是一个三角形数（阶乘的加法等效项） http://en.wikipedia.org/wiki/Triangular_number

加法次数 N^2 + N / 2

然而，这并没有考虑分离数字所需的工作量。

- StuartLC

Answer 6

这不是一个新的答案，而是对Gabe所给出的已接受答案的阐述。

假设数字为19，则总和为

1+9+19
= 1+ 9 + (10*1+9)
= 11*1 + 2*9

如果数字是486，那么总和就是

= 4 + 8 + 6 + 48+ 86 +486
= 4 + 8 + 6 + (10*4+8) + (10*8+6) + (100*4+10*8+6)
= 111*4+22*8+3*6

一般来说，如果一个数字被表示为由数字"XY"组成的字符串，那么子字符串的总和可以计算为：

sum of XY  = X +Y + (10X+Y) 
= 11X+2Y

sum of XYZ = X + Y + Z + (10X + Y)+ (10 Y+ Z) + (100X+ 10Y+Z)
= 111X+22Y+3Z

sum of XYZW = x+ y+ z + w + (10x + y) + (10y+ z)+ (10z+ w)+(100X+ 10Y+Z)+(100y+ 10z+w)+(1000x+100y+10z+w)
=1111x+222y+33z+4w

对于9位数字，求和为

(9 times 1)*1st + (8 times 2)*2nd+ (7 times 3)*3rd + (6 times 4)*4th+(5 times 5)*5th +(4 times 6)*6th  +(3 times 7)*7th+(3 times 8)*8th+(3 times 9)*9th

- Kaushik Lele