LeetCode 306. 累加数
题目描述
✅ 306. 累加数
题意分析
将数字字符串从左到右完整切分成至少三个非负整数，使第三项开始的每一项都等于前两项之和，判断是否存在这样的切分。每个字符都必须使用，不能改变顺序或只验证其中一段。
每个整数至少包含一位。单独的零合法，但多位整数不能带前导零；这条规则约束每一项，而不是禁止字符串中出现零。字符串里的整数可能超过固定宽度类型，因此还要处理整体转整数时的溢出问题。
解法：枚举前两段 + 字符串加法验证
核心思路
[!blue]
真正需要尝试的只有前两个数的结束位置。选定它们后，第三个数必须是两者之和，第四个数也随之确定，后面不存在任意切分的自由。因此枚举前两项，再沿着唯一确定的累加关系验证后缀，比对每一项都继续枚举切点更直接。
用
firstEnd和secondEnd表示两个右开切点，前两项分别为[0, firstEnd)和[firstEnd, secondEnd)。两项都要非空，且secondEnd < n，为第三项至少留一个字符。若某项首位为零，它只能取一位，再延长必然违反规则，可以结束对应切点枚举。验证时，
first、second保存上一对加数，index指向尚未使用的字符串起点。计算它们的精确和sum，要求从index开始的文本与整个sum完全相同；匹配后推进sum.length个字符，并把加数滚动为second、sum。任意一次不匹配都能确定当前前两项选择不可行，必须换切点，不能跳过字符继续找。求和使用十进制字符串加法：两个指针从加数末尾出发，逐位计算当前数字和与进位，把个位写入逆序缓冲区，把十位传给下一轮。某一侧已经读完时只使用另一侧，最后的进位也要处理；完成后反转缓冲区得到正常顺序的和。每轮只计算两个数字与一个进位，无需将完整长数转成整数。
还可以提前排除长度不够的切分。两个合法非负整数的和，位数至少等于较长加数的位数；若剩余字符比这个长度还短，下一项已经放不下。继续延长第二项只会让剩余字符更少、较长加数不变或更长，因此可以直接结束当前内层枚举。
只有验证指针恰好到达字符串末尾才成功。由于枚举时一定留下了第三项的位置，而每次匹配至少前进一位，成功同时保证了项数不少于三、所有字符被完整使用、每个后续数都满足累加关系。
解题步骤
- 枚举第一项右开切点
firstEnd，至少为后面两项保留位置；多位前导零时结束外层枚举。- 枚举第二项右开切点
secondEnd，保留至少一个后缀字符；多位前导零或剩余长度不足下一项时结束内层枚举。- 取出前两项，从
secondEnd开始验证后缀。- 用字符串逐位加法计算下一项，检查剩余文本是否以这个完整结果开头；不匹配则当前切分失败。
- 匹配后推进下标并滚动两个加数，重复验证直到末尾；任意一组切点成功即返回
true。- 所有初始切分都失败，则返回
false。
代码实现
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)$，保存当前两项、相加缓冲区与结果字符串，不需要记录完整切分或递归搜索树。
关键点总结
[!green]
- 只对前两项分支，之后的每一个值和长度都由加法唯一决定。
- 前导零只允许单独的一位零，初始两项合法后，字符串加法也会生成规范数字表示。
- 剩余长度剪枝利用非负加法的位数下界，扩大第二项后不会重新变得可行。
- 字符串加法覆盖题目关于大整数的进阶，成功条件是完整消费后缀。
易错点总结
[!yellow]
- 用固定宽度整数解析整段，遇到超过该类型范围的合法长数会溢出或解析失败。
- 完全禁止数字零，或允许多位数保留前导零，都不符合切分规则。
- 第二项一直取到字符串末尾，会在根本没有第三项时错误成功。
- 只匹配第三项就返回，会忽略后续字符是否继续满足累加关系。
- 字符串加法漏掉最后进位，或忘记把从低位生成的缓冲区反转，会得到错误的和。
- Go 截取待比较区间前不检查剩余长度，会在下一项超出后缀时触发越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 842. 将数组拆分成斐波那契序列 | 中等 | 验证规则同为后项等于前两项和，原题还需返回实际数列并受整数范围限制。 |
| 415. 字符串相加 | 简单 | 数字可能很长时，逐位字符串加法可用于核对下一段，避免整体转整数溢出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！