一、题目描述
题目：累加数
难度：中等
地址：《306》累加数
描述：累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数 不会 以 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）组成
二、题目解析
本题的核心在于不断的从找到连续的三个数字进行累加，首先我们可以枚举前两个数的所有情形：
- 满足条件的第一个数的范围最大是
n//2+1 - 满足条件的第一个数的范围最大是
n//3*2+1
对于第三个数主要思想是：
因为第三个数是前两个数的加和，因此第三个数的长度最短也要与前二者最长的相同， 因此从第二个数的末尾开始，确定长度，每次多加一位数，如果得到的数字比前两数的加和大则判断失败，退出判断循环。判断成功则继续判断。
最后我们需要在找到第三个数的时候进行相等判断，假设三个数为a,b,c如果a+b=c则调整a=b,b=c并重新按照条件寻找c，寻找的位置从上一次c(调整后的b)的位置之后开始。图示如下：
三、解题代码
解法（一）
class Solution: def isAdditiveNumber(self, num: str) -> bool: # 数组小于3时，构不成累加数 n = len(num) if n < 3: return False # 确定第一个数的范围（最长不超过一半） for i in range(1, n // 2 + 1): # 确定第二个数的范围（最长不超过2/3） for j in range(i + 1, n // 3 * 2 + 1): # 得到第一、二个数（排除0开头的情况） a = int(num[0:i]) if num[0] != '0' else int(num[0]) b = int(num[i:j]) if num[i] != '0' else int(num[i]) m = j + 1 ''' 接下来确定第三个数,主要思想是： 因为第三个数是前两个数的加和，因此第三个数的长度最短也要与前二者最长的相同， 因此从第二个数的末尾开始，确定长度，每次多加一位数，如果得到的数字比前两数的 加和大则判断失败，退出判断循环。 判断成功则继续判断 ''' while m <= n: c = int(num[j:m]) if num[j] != '0' else int(num[j]) # 定义一个标记，作为第三个数字进行变更的标记（上一次成功累加则变更） add = -1 # 如果累加数a+b=c则进行数据替换，a=b,b=c,c=num[m,m+(m-j)] if c == a + b: print(a, b, c) a = b b = c add = m - j j = m m = m + add continue elif c > a + b or m - j > max(j - i, i): break m += 1 else: # 如果持续变更到末尾，累加数不为-1则返回True if add != -1: return True return False
解法（二）
枚举所有可能出现的情况，按照满足题意的方式去组合字符串，最终判断是否能够组合出和原字符串相同的字符串，如果出现则返回True。
class Solution: def isAdditiveNumber(self, num: str) -> bool: n = len(num) for i in range(1, n // 2 + 1): for j in range(i + 1, n // 3 * 2 + 1): a = int(num[:i]) b = int(num[i:j]) # 数值转字符串拼接 res = f'{a}{b}' while len(res) < n: a, b, res = b, a + b, res + str(a + b) if res == num: return True return False
