如何找到数字的所有子串之和的最优解?
例如,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;
}
2+3
用于1234
吗? - codaddict