LeetCode 306. 累加数
目录
题目描述
✅ 306. 累加数
题意分析
输入是一个只含数字字符的字符串
num，要判断能否在它中间插入若干刀，把它切成至少三个数，使得从第三个数开始，每个数都恰好等于紧邻它前面两个数之和。切分必须是连续且不重不漏的，也就是说所有段拼起来必须还原成原串。有两处约束信号必须抠住。第一，不允许非法前导零：合法的段要么是单个字符
0，要么首字符不为0。所以"1023"不能切成1, 0, 23之外的形式去凑，"01"这种段一律非法。第二，题面明确提示数字可能非常长，长到超出 64 位整数范围，这实际上是在告诉你不要走parseLong那条路。最有价值的结构性观察是：这个序列由前两个数完全决定。一旦第一段和第二段定下来，第三段必须是它们的和，第四段必须是第二三段的和，整条链没有任何自由度。所以搜索空间不是「所有切分方式」的指数级，而只是「前两段的切点」这一对下标。
边界情况包括：串长小于 3 时不可能凑出三个数；单独的
"0"、"00"、"000"要分别判断（"000"可以切成0, 0, 0是合法的，"00"只有两段不合法）；某一段的和可能比剩余字符串还长，此时应当直接判失败而不是越界访问。
解法：枚举前两段 + 字符串加法验证
核心思路
累加序列至少有三个数，且从第三个数开始，每一项都由前两项唯一确定。普通回溯会在每个位置枚举下一个切点；本题可以把回溯树压缩为：只枚举前两个数的结束位置，后续不断计算两数之和并匹配字符串前缀。
数字段可能超过 64 位整数范围，不能用
long解析。用十进制字符串模拟加法：从末位向前相加，维护进位，最后反转结果。这样数值长度只受输入字符串限制。前导零规则必须在枚举时处理：单独的
"0"合法，但"01"非法。前两个数确定后，若其和不是剩余字符串的前缀，该分支立即失败；若能逐段恰好消费完整个字符串，则得到合法累加序列。正确性来自两点：任意合法序列的前两个切点都会被双重循环枚举到；而这两个数一旦确定，后续没有其他选择，逐项匹配通过当且仅当整条序列满足累加关系。
解题步骤
- 枚举第一个数的结束位置；若它以
0开头，长度只能为1。- 枚举第二个数的结束位置，并应用同样的前导零规则。
- 若剩余长度小于两个加数的最大长度，连下一项都放不下，结束当前内层枚举。
- 用字符串加法算出下一项；检查它是否从当前下标开始精确匹配。
- 匹配后将两个加数向前滚动，直到字符串恰好消费完；任一位置不匹配则尝试下一组初始切点。
例如
"199100199"选择前两项"1"、"99"后，依次得到并匹配"100"、"199"，最终恰好到达末尾，因此返回true。
代码实现
class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int firstEnd = 1; firstEnd < n - 1; firstEnd++) {
if (num.charAt(0) == '0' && firstEnd > 1) {
break;
}
for (int secondEnd = firstEnd + 1; secondEnd < n; secondEnd++) {
if (num.charAt(firstEnd) == '0' && secondEnd - firstEnd > 1) {
break;
}
int maxAddendLength = Math.max(firstEnd, secondEnd - firstEnd);
if (n - secondEnd < maxAddendLength) {
break;
}
String first = num.substring(0, firstEnd);
String second = num.substring(firstEnd, secondEnd);
if (matchesRest(num, secondEnd, first, second)) {
return true;
}
}
}
return false;
}
private boolean matchesRest(String num, int index, String first, String second) {
while (index < num.length()) {
String sum = add(first, second);
if (!num.startsWith(sum, index)) {
return false;
}
index += sum.length();
first = second;
second = sum;
}
return true;
}
private String add(String first, String second) {
StringBuilder reversed = new StringBuilder();
int i = first.length() - 1;
int j = second.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int sum = carry;
if (i >= 0) {
sum += first.charAt(i--) - '0';
}
if (j >= 0) {
sum += second.charAt(j--) - '0';
}
reversed.append(sum % 10);
carry = sum / 10;
}
return reversed.reverse().toString();
}
}
func isAdditiveNumber(num string) bool {
n := len(num)
for firstEnd := 1; firstEnd < n-1; firstEnd++ {
if num[0] == '0' && firstEnd > 1 {
break
}
for secondEnd := firstEnd + 1; secondEnd < n; secondEnd++ {
if num[firstEnd] == '0' && secondEnd-firstEnd > 1 {
break
}
maxAddendLength := firstEnd
if secondEnd-firstEnd > maxAddendLength {
maxAddendLength = secondEnd - firstEnd
}
if n-secondEnd < maxAddendLength {
break
}
first := num[:firstEnd]
second := num[firstEnd:secondEnd]
if matchesAdditiveRest(num, secondEnd, first, second) {
return true
}
}
}
return false
}
func matchesAdditiveRest(num string, index int, first string, second string) bool {
for index < len(num) {
sum := addDecimalStrings(first, second)
if len(num)-index < len(sum) || num[index:index+len(sum)] != sum {
return false
}
index += len(sum)
first, second = second, sum
}
return true
}
func addDecimalStrings(first string, second string) string {
reversed := make([]byte, 0, len(first)+len(second))
i, j, carry := len(first)-1, len(second)-1, 0
for i >= 0 || j >= 0 || carry != 0 {
sum := carry
if i >= 0 {
sum += int(first[i] - '0')
i--
}
if j >= 0 {
sum += int(second[j] - '0')
j--
}
reversed = append(reversed, byte(sum%10)+'0')
carry = sum / 10
}
for left, right := 0, len(reversed)-1; left < right; left, right = left+1, right-1 {
reversed[left], reversed[right] = reversed[right], reversed[left]
}
return string(reversed)
}
复杂度分析
设字符串长度为
n。
- 时间复杂度：$O(n^3)$。前两个切点有 $O(n^2)$ 种组合，每组最多用 $O(n)$ 的字符运算验证后续序列。
- 空间复杂度：$O(n)$。字符串加法产生的结果和缓冲区长度最多为 $O(n)$；没有保存整棵回溯树。
关键点总结
- 回溯只需在前两个切点处分支，第三项起由前两项之和唯一确定。
- 不能依赖固定宽度整数；字符串加法同时解决 Java 和 Go 的大数溢出问题。
- 验证成功的条件是整个字符串被恰好消费完，不是只匹配出一个和。
- 前导零规则是“长度大于
1时首位不能为0”，所以"000"合法。- 剩余长度不足下一项的最小可能长度时可以安全剪枝。
易错点总结
- 使用
Long.parseLong或strconv.ParseInt，遇到超长数字会溢出。- 完全禁止数字
0会错判"000"；允许"01"又会引入非法切分。- 只验证第三项就返回，会把后续不满足关系的字符串误判为合法。
- 第二个切点取到字符串末尾，会在没有第三个数时错误成功。
- 字符串加法遗漏最终进位或忘记反转，会在
"99" + "1"这类用例中出错。- Go 中截取前缀前未检查剩余长度，会触发切片越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 842. 将数组拆分成斐波那契序列 | 中等 | 同构问题并要求还原具体方案 |
| 93. 复原 IP 地址 | 中等 | 定段数切分与合法性剪枝 |
| 131. 分割回文串 | 中等 | 回溯枚举切点并逐段校验 |
| 140. 单词拆分 II | 困难 | 记忆化搜索枚举全部拆分 |
| 472. 连接词 | 困难 | 字典树配合拆分可行性判定 |
| 241. 为运算表达式设计优先级 | 中等 | 分治按运算符切分并合并结果 |