当前位置：首页 > news >正文

LeetCode题练习与总结：累加数--306

news 2025/7/8 5:57:42

一、题目描述

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须至少包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数，除数字 0 之外，不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1：

输入："112358"
输出：true 
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：

输入："199100199"
输出：true 
解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

提示：

1 <= num.length <= 35
num 仅由数字（0 - 9）组成

二、解题思路

首先需要确定前两个数，由于题目要求至少包含3个数，且序列中的每个后续数字必须是它之前两个数字之和，因此，我们可以通过遍历字符串的前半部分来尝试每一种可能的前两个数。
在确定前两个数之后，我们就可以通过循环来判断后续的数是否满足累加序列的条件。
需要注意的是，由于累加序列里的数不会以0开头（除了数字0本身），所以在确定数字时，要排除掉以0开头的多位数字。
为了避免数字溢出，我们可以使用字符串来处理数字的加法。

三、具体代码

class Solution {public boolean isAdditiveNumber(String num) {int n = num.length();for (int i = 1; i <= n / 2; i++) {for (int j = 1; j <= (n - i) / 2; j++) {if (check(num.substring(0, i), num.substring(i, i + j), num.substring(i + j))) {return true;}}}return false;}private boolean check(String num1, String num2, String remaining) {// 检查以0开头的多位数字if ((num1.length() > 1 && num1.startsWith("0")) || (num2.length() > 1 && num2.startsWith("0"))) {return false;}String sum = add(num1, num2);if (remaining.equals(sum)) {return true;}if (!remaining.startsWith(sum)) {return false;}return check(num2, sum, remaining.substring(sum.length()));}private String add(String num1, String num2) {int carry = 0;StringBuilder sum = new StringBuilder();int i = num1.length() - 1, j = num2.length() - 1;while (i >= 0 || j >= 0 || carry != 0) {int n1 = i >= 0 ? num1.charAt(i--) - '0' : 0;int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;int s = n1 + n2 + carry;sum.append(s % 10);carry = s / 10;}return sum.reverse().toString();}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

两层循环确定前两个数：外层循环变量 i 遍历从 1 到 n/2，内层循环变量 j 遍历从 1 到 (n-i)/2。因此，循环的次数是 O(n^2)。
递归调用 check 方法：在每次循环中，我们都会调用 check 方法，这个方法在最坏的情况下可能会递归 n 次（每次递归处理一个数字，直到处理完整个字符串）。每次递归调用都会进行一次字符串加法操作。
字符串加法操作 add：字符串加法操作的时间复杂度是 O(max(len(num1), len(num2)))，其中 len(num1) 和 len(num2) 分别是字符串 num1 和 num2 的长度。在最坏的情况下，num1 和 num2 的长度可能接近 n/2，因此字符串加法的时间复杂度是 O(n)。

综上所述，总的时间复杂度是两层循环的时间复杂度乘以每次循环中 check 方法的递归调用时间复杂度，再乘以每次递归调用的字符串加法时间复杂度。即：

时间复杂度 = O(n^2) * O(n) * O(n) = O(n^4)

2. 空间复杂度

递归调用栈：在 check 方法的递归过程中，最坏情况下递归深度为 n，因此递归调用栈的空间复杂度是 O(n)。
字符串存储：在 add 方法中，我们使用了一个 StringBuilder 来存储加法的结果，其空间复杂度是 O(n)。
递归参数：每次递归调用 check 方法时，都会传递三个字符串参数，但需要注意的是，这些字符串是原始字符串的子串，并没有额外的空间消耗。

综上所述，总的空间复杂度主要取决于递归调用栈和字符串加法操作中的 StringBuilder，因此：

空间复杂度 = O(n) + O(n) = O(n)

五、总结知识点

字符串处理：
- 使用 substring 方法提取字符串的子串。
- 使用 startsWith 方法检查字符串是否以特定子串开头。
- 使用 equals 方法比较两个字符串是否相等。
迭代与递归：
- 使用两层嵌套循环来尝试不同的前两个数组合。
- 使用递归方法 check 来验证后续的数字是否满足累加序列的条件。
字符串与数字的转换：
- 使用 charAt 方法获取字符串中的字符，并将其转换为对应的整数值（通过减去字符 ‘0’）。
数学运算：
- 实现字符串形式的数字加法，考虑到进位（carry）。
数据结构：
- 使用 StringBuilder 来构建字符串，因为它在频繁修改字符串时比使用 String 更高效。
逻辑判断：
- 在 check 方法中，判断以0开头且长度大于1的字符串是否符合累加序列的条件。
边界条件处理：
- 在 add 方法中，当两个数字的长度不相同时，需要处理较短的数字已经遍历完的情况。
递归终止条件：
- 在 check 方法中，递归终止的条件是当剩余的字符串与计算出的和相等，或者剩余的字符串不以计算出的和开头。