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 <= 35num仅由数字（0-9）组成
**进阶：**你计划如何处理由过大的整数输入导致的溢出?
题解
思路
题目中说到：“一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和” ，因此我们可以知道，对于整个答案数字的划分是建立在最开始的两个数字之上，也就是说我们只要确认了开始的两个数字也就可以确定整一个的累加序列数组。
- 1、枚举第一个数
- 2、枚举第二个数
- 3、计算两数之和
- 4、判断两数之和是否存在于下一个数，存在则将第二个数作为第一个数、两数之和作为第二个数，重复步骤三，不存在则回到步骤二
准备
大数相加
在此之前我们还需要准备一个函数来进行辅助计算，解决题目中说到的“你计划如何处理由过大的整数输入导致的溢出”，我们可以使用字符串来完成大数相加。
let getSum = (a, b) => { a = a.split(""); b = b.split(""); let res = "", flag = 0; while (a.length > 0 || b.length > 0) { let a1 = a.pop() || 0; let b1 = b.pop() || 0; let c = parseInt(a1) + parseInt(b1) + flag; flag = Math.floor(c / 10); res = (c % 10) + res; } if (flag > 0) res = flag + res; return res; };
递归判断两数之和
let judge = (start, first, second) => { if (start === num.length) { ret = true; return; } if (start > num.length) return; let res = getSum(first, second); if (res === num.slice(start, start + res.length)) { judge(start + res.length, second, res); } };
完整代码
/** * @param {string} num * @return {boolean} */ var isAdditiveNumber = function (num) { let getSum = (a, b) => { a = a.split(""); b = b.split(""); let res = "", flag = 0; while (a.length > 0 || b.length > 0) { let a1 = a.pop() || 0; let b1 = b.pop() || 0; let c = parseInt(a1) + parseInt(b1) + flag; flag = Math.floor(c / 10); res = (c % 10) + res; } if (flag > 0) res = flag + res; return res; }; let judge = (start, first, second) => { if (start === num.length) { ret = true; return; } if (start > num.length) return; let res = getSum(first, second); // console.log(start, first, second, res); if (res === num.slice(start, start + res.length)) { judge(start + res.length, second, res); } }; let first = "", second = "", ret = false; for (let i = 0; i < num.length; i++) { first += num[i]; second = ""; for (let j = i + 1; j < num.length; j++) { if (second === "0") break; second += num[j]; if (ret) return true; else { if (second.length <= num.length - j) judge(j + 1, first, second); } } } return false; };
