数字的子串之和
求一个数字的子串之和的最佳解决方案是什么？
例如，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;
}
What is the optimal solution to find the sum of substring of a number ?
For example, Sum (123) = 1 + 2 + 3 + 12 + 23 + 123 = 164.
I think it is O(n^2). because
sum = 0
for i in number: // O(n)
sum += startwith(i) // O(n)
return sum
Any optimal solution? What is the best approach?
Here is my solution but 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;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
请注意：
这是我的 C# 实现，尽管移植到 Java 应该很简单：
请注意，它实际上是 O(n)。
Observe that:
Here's my C# implementation, though it should be trivial to port to Java:
Note that it is effectively O(n).
对于长度为 n 的给定字符串，肯定有 ~N^2 个可能的子串。但是，我们可以使用以下等式在线性时间内计算总和：
S 代表数字序列 ( s0, s1, s2, ... , sn)。
对于S＝<1,2,3>它返回 111*1+22*2+3*3=164
请注意，如果我们事先计算 10 的 N 次方，或者在循环过程中逐步计算，则运行时间是线性。
There are definitely ~N^2 possible substrings of a given string of length n. However, we CAN compute the sum in linear time, using the following equation:
S stands for the sequence of digits (s0, s1, s2, ... , sn).
For S=<1,2,3> it returns 111*1+22*2+3*3=164
Note that the running time is linear if we compute the N powers of 10 beforehand, or progressively during the loop.
正如 @Gabe 提供的，你可以这样做：
你可以在 O(n) 中计算 A0-An
现在计算 b[i]：
你可以在 O(n) 中计算所有 b[i]
现在有些是
[伪代码]
As @Gabe offered you can do:
you can compute A0-An in O(n)
now compute b[i]:
you can compute all b[i] in O(n)
Now the some is
[Pseudo code]
上面所有的答案看起来都很棒。我最近正在解决类似的问题。上面给出的公式效果很好，但是正如您所看到的，随着字符串长度的增加，计算变得困难并且解决方案非常大。通常，当字符串的长度非常大时，您会被要求在 MOD 后给出一个很大的数字（例如 1000000007）。因此，现在您可以使用一点模块化算术轻松计算值，或者具体地说 模幂 和 乘法逆元。因此，针对大输入修改后的新公式可以写为：
假设。
这是代码：
就是这样。
All the above answers looks great. I was recently solving a similar problem. The formula presented above works well but as you can see as the length of the string increases the computation becomes difficult and the solution really large. Usually when the length of the string is really large you will be asked to give the answer after MOD a large number say 1000000007. So now you can easily compute the values using little bit of modular Arithmetic, or to be specific Modular exponentiation and Multiplicative inverse. So the new formula after modification for large inputs can be written as.
Assumption made.
Here is the code:
That's it.
FWIW N 位数字相加的整数个数似乎是
N + N-1 + N-2 ... 1
这是一个三角数（阶乘的加法等价）
http://en.wikipedia.org/wiki/Triangle_number
添加的数量
N^2 + N / 2
但是，这没有考虑拆分数字所需的工作
FWIW the number of integers to add for number of N digits appears to be
N + N-1 + N-2 ... 1
Which is a triangular number (additive equivalent of a factorial)
http://en.wikipedia.org/wiki/Triangular_number
The number of additions
N^2 + N / 2
However, this doesn't consider the work needed to split out the digits
这不是一个新答案，而是对加布给出的已接受答案的阐述。
假设数字是 19，则总和为
如果数字为 486，则总和为
所以一般而言，如果数字表示为数字字符串“XY”，则子字符串的总和将是该数字可以计算为
对于 9 位数字总和是
Not a new answer but elaboration of accepted answer given by Gabe.
Say number is 19 then sum is
If number is 486 then sum is
So in general term if a number is represented as a string of digits "XY" then sum of sub-strings will bw that number can be calculated as
For 9 digit number sum is