来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/additive-number

题目描述

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

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

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

解题思路

本题核心思想是，确定了前两个数便可以确定整个序列的数。考虑到数字规模仅仅35，所以可以暴力枚举所有前两个数，并判断后续数字是否满足累加数。

首先外循环，循环枚举不同长度的前两个数，这里可以优化的点是如果第一个数的长度超过了整个序列容量的一半，那么就不必枚举下去了，因为一个大数加上任何非负数，都不会减小，所以位数肯定不会变少。

确定了前两个数的位数，便可以依次判断后续的数是否满足累加数的定义，为了兼容过大的整数，在这里我使用了逆序字符串相加求和的方法代替了整数求和。

首先将前两个数提取出来，注意，这两个数的存储形式是逆序存储的，也就是将123存放为321，这样是由于求和操作是从低位相加会比较方便计算。顺便判断这两个数是否为0开头，如果是0开头并且不为0，那么根据题意并不符合累加数。

接着进行两数求和，注意进位的问题，并且如果求和结束后还有溢出需要再增加一位。判断剩余的序列长度是否比和的长度长，如果不满足，那么就没必要判断了，肯定不符合累加数，接着从和的尾部依次与剩余序列进行匹配，如果不相同，那么就不为累加数。最终如果满足所有的条件，那么就是累加数。

 

代码展示

class Solution {
public:
    bool check(int iIndex1, int iIndex2, const string &num)
    {
        int iIndex3 = iIndex2 + 1;
        string strNum1, strNum2, strSum;
        for (int i = iIndex1; i >= 0; i--)
        {
            strNum1.push_back(num[i]);
        }
        if (strNum1.size() != 1 && strNum1[strNum1.size() - 1] == '0')
            return false;
        for (int i = iIndex2; i > iIndex1; i--)
        {
            strNum2.push_back(num[i]);
        }
        if (strNum2.size() != 1 && strNum2[strNum2.size() - 1] == '0')
            return false;
        while (iIndex3 < num.size())
        {
            int iFlag = 0;
            for (int i = 0; i < max(strNum1.size(), strNum2.size()); i++)
            {
                int iSum = (i < strNum1.size() ? strNum1[i] - '0' : 0) + (i < strNum2.size() ? strNum2[i] - '0' : 0) + iFlag;
                iFlag = iSum / 10;
                strSum.push_back(iSum % 10 + '0');
            }
            if (iFlag)
                strSum.push_back(iFlag + '0');
            if (num.size() - iIndex3 < strSum.size())
                return false;
            for (int i = strSum.size() - 1; i >= 0; i--)
            {
                if (strSum[i] != num[iIndex3])
                    return false;
                iIndex3++;
            }
            strNum1 = strNum2;
            strNum2 = strSum;
            strSum.clear();
        }
        return true;
    }
    bool isAdditiveNumber(string num) {
        for (int i = 0; i <= num.size() / 2; i++)
        {
            for (int j = i + 1; j < num.size() - 1; j++)
            {
                if (check(i, j, num))
                {
                    return true;
                }
            }
        }
        return false;

    }
};

 

运行结果