LeetCode 306. 累加数

Categories:

题目描述
思路分析
1. 解法一：枚举前两项 + 字符串加法校验（推荐）
相似题目

题目描述

✅ 306. 累加数

思路分析

解法一：枚举前两项 + 字符串加法校验（推荐）

核心思路：

枚举前两段数字的切分位置，注意前导零的合法性。

之后通过字符串加法生成下一项，并与原字符串按前缀对齐验证。

若能完整覆盖字符串，则为累加数。

复杂度分析：

时间复杂度：O(n^3)，其中 n 表示字符串长度，枚举与校验都与 n 成正比。

空间复杂度：O(n)，其中 n 表示字符串加法的临时结果长度。

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i <= n - 2; i++) {
            if (num.charAt(0) == '0' && i > 1) {
                break;
            }
            for (int j = i + 1; j <= n - 1; j++) {
                if (num.charAt(i) == '0' && j - i > 1) {
                    break;
                }
                String a = num.substring(0, i);
                String b = num.substring(i, j);
                int k = j;

                while (k < n) {
                    String c = addStrings(a, b);
                    if (!num.startsWith(c, k)) {
                        break;
                    }
                    k += c.length();
                    a = b;
                    b = c;
                }

                if (k == n) {
                    return true;
                }
            }
        }
        return false;
    }

    private String addStrings(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {
            int da = i >= 0 ? a.charAt(i) - '0' : 0;
            int db = j >= 0 ? b.charAt(j) - '0' : 0;
            int sum = da + db + carry;

            sb.append(sum % 10);
            carry = sum / 10;
            i--;
            j--;
        }

        return sb.reverse().toString();
    }
}

func isAdditiveNumber(num string) bool {
	n := len(num)
	for i := 1; i <= n-2; i++ {
		if num[0] == '0' && i > 1 {
			break
		}
		for j := i + 1; j <= n-1; j++ {
			if num[i] == '0' && j-i > 1 {
				break
			}

			a := num[:i]
			b := num[i:j]
			k := j

			for k < n {
				c := addStrings(a, b)
				if k+len(c) > n || num[k:k+len(c)] != c {
					break
				}
				k += len(c)
				a, b = b, c
			}

			if k == n {
				return true
			}
		}
	}
	return false
}

func addStrings(a, b string) string {
	i := len(a) - 1
	j := len(b) - 1
	carry := 0
	buf := make([]byte, 0)

	for i >= 0 || j >= 0 || carry > 0 {
		da := 0
		db := 0
		if i >= 0 {
			da = int(a[i] - '0')
		}
		if j >= 0 {
			db = int(b[j] - '0')
		}
		sum := da + db + carry
		buf = append(buf, byte(sum%10)+'0')
		carry = sum / 10
		i--
		j--
	}

	for l, r := 0, len(buf)-1; l < r; l, r = l+1, r-1 {
		buf[l], buf[r] = buf[r], buf[l]
	}
	return string(buf)
}

相似题目

题目	难度	考察点
842. 将数组拆分成斐波那契序列	中等	回溯、剪枝
415. 字符串相加	简单	字符串模拟
43. 字符串相乘	中等	字符串模拟
989. 数组形式的整数加法	简单	数组模拟
306. 累加数	中等	回溯、字符串处理

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/49995072