跳到主要内容

306.累加数

· 阅读需 7 分钟

1、题干​

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

一个有效的 累加序列 必须 至少 包含 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）组成

 

进阶：你计划如何处理由过大的整数输入导致的溢出?

2、解法1-回溯​

总体思路：使用回溯对所有可能性进行匹配直到成功。大体步骤如下：

  • 使用递归实现回溯算法，递归函数match，参数l、m、r分别表示待匹配的3个数的起始位置
  • match函数第一步先处理边界情况、0开头的特殊情况
  • 第二步从num字符串中取出前两个数并求和，得到第三个数n3
  • 第三步剪枝，如果剩余字符比要查找的结果更短，直接返回false
  • 第四步在剩余字符串中查找n3是否存在，若存在且正好用尽所有字符则返回true
  • 若不存在则尝试r右移一位以及m右移一位的情况

注意点

  • 测试用例中不存在大整数，因此没有做大整数特殊处理
  • 边界条件、特殊情况略多，如果不能AC可以多调试看看是否边界没处理好
  • 一定要剪枝，否则大概率会超时

3、代码​

var isAdditiveNumber = function (num) {
    function match(l, m, r) {
        // 处理边界情况、特殊情况（0开头的数）
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        const n3 = `${+num.slice(l, m) + +num.slice(m, r)}`;
        // 剪枝：如果剩余字符比要查找的结果更短，直接返回false
        if (n3.length > num.length - r) return false;
        // 匹配成功 🚀🚀🚀
        if (num.slice(r, r + n3.length) === n3 && (r + n3.length === num.length || match(m, r, r + n3.length))) return true;

        // 匹配失败：尝试查找其他可能性
        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

4、执行结果​

执行用时: 108 ms 内存消耗: 44.7 MB


5、解法1-优化版​

  • 问题1：确定开头两个数字之后（num.slice(r, r + n3.length) === n3）的后续匹配方式存在无效遍历，原先使用递归进行后续匹配，每次右移1位，因此存在大量无效匹配。
  • 问题2：已遍历过的情况没有直接跳过，导致存在大量重复遍历。
  • 优化1：确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。
  • 优化2：使用哈希表记录已遍历过的情况，后续直接跳过这些情况，进行记忆化搜索。（感谢评论区 @Jvaeyhcd 的提醒）

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到99次。


6、代码​

var isAdditiveNumber = function (num) {
    const set = new Set();

    function match(l, m, r) {
        if (set.has(`${l}-${m}-${r}`)) return false;
        set.add(`${l}-${m}-${r}`);
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (r - m > num.length - r || m - l > num.length - r) return false;

        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        let r2 = r, n1 = +num.slice(l, m), n2 = +num.slice(m, r), n3 = n1 + n2;
        while (num.slice(r2, r2 + `${n3}`.length) === `${n3}`) {
            (r2 = r2 + `${n3}`.length), (n1 = n2), (n2 = n3), (n3 = n1 + n2);
        }
        if (r2 === num.length) return true;

        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

7、执行结果​

执行用时: 68 ms 内存消耗: 38.1 MB


8、解法2-双指针遍历​

总体思路：双层遍历确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到120次。


9、代码​

var isAdditiveNumber = function (num) {
    for (let m = 1; m < num.length; m++) {
        let n1 = +num.slice(0, m);
        if (num[0] === '0' && m > 1) return false;

        for (let r = m + 1; r < num.length; r++) {
            if (num[m] === '0' && r - m > 1) break;
            let n2 = +num.slice(m, r), r_2 = r, n_1 = n1, n3 = n1 + n2;
            while (num.slice(r_2, r_2 + `${n3}`.length) === `${n3}`) {
                (r_2 = r_2 + `${n3}`.length), (n_1 = n2), (n2 = n3), (n3 = n_1 + n2);
            }
            if (r_2 === num.length) return true;
        }
    }

    return false;
};

10、执行结果​

执行用时: 60 ms 内存消耗: 38.1 MB

1.png