力扣-306. 累加数

累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
                  //第二个字符开始位置                                                                   
            for(int secondStart = 1;secondStart < n-1; secondStart++){
                  //如果第一个字符为0那么第一个数字就是0，然后第二个数字的开始位置必为1                                             
                if(num[0] == '0' && secondStart != 1){
                    break;
                }
                  //第二个字符结束位置                                                                                
                for(int secondEnd = secondStart; secondEnd < n-1; secondEnd++){
                      //如果第二个字符开始位置为0那么第二个数字就是0，然后第二个数字的结束位置必为开始位置                                                                                               
                    if(num[secondStart] == '0' && secondStart != secondEnd) {
                        break;
                    }
                      //前去判断                                                                          
                    if(valid(secondStart, secondEnd, num)) {
                        return true;
                    }
                }
            }
        return false;
    }

    //判断函数                                                           
    bool valid(int secondStart, int secondEnd, string num) {
        int n = num.size();
        int firstStart = 0, firstEnd = secondStart - 1;
        while(secondEnd <= n - 1){
             //运用 stringAdd获得third的结果字符串                                                                           
            string third = stringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
            int thirdStart = secondEnd + 1;
            int thirdEnd = secondEnd + third.size();
             //判断third的结果字符串和num从thirdStart到thirdEnd截取的字符串是否相等                                                                                              
            if(thirdEnd >= n || !(num.substr(thirdStart, thirdEnd - thirdStart + 1) == third)){
                break;
            }
            if(thirdEnd == n - 1) {
                return true;
            }
                                 
             //接下来考虑第4个数、第5个数.................                                     
            firstStart = secondStart;
            firstEnd = secondEnd;
            secondStart = thirdStart;
            secondEnd = thirdEnd;
        }
        return false;
    }

// 根据firstStart、firstEnd、secondStart、secondEnd获取third字符串                                       
    string stringAdd(string s, int firstStart, int firstEnd, int secondStart, int secondEnd) {
        string third;
         //carry存储高位 cur存储低位                                          
        int carry = 0, cur = 0;
        while(firstEnd >= firstStart || secondEnd >= secondStart || carry != 0){
            cur = carry;
            if (firstEnd >= firstStart) {
                cur += s[firstEnd] - '0';
                --firstEnd;
            }
            if (secondEnd >= secondStart) {
                cur += s[secondEnd] - '0';
                --secondEnd;
            }
             //取商是获得当前位的进位数                       
            carry = cur / 10;
             //取余是获得当前位   
            cur %= 10;
             //把当前位放进去                                     
            third.push_back(cur + '0');
        }
         //由于高位在后面，低位在前面，所以需要倒置                                     
        reverse(third.begin(), third.end());
        return third;
    }
};

这里是暴力解题，0在序列中多字符组成的数字中任意一个位置不能作为第一个字符，定义了firstStart、firstEnd、secondStart、secondEnd来存储第一和二个数字的开始位置和截止位置、然后用thirdStart、thirdEnd来验证、验证成功后用firstStart、firstEnd、secondStart、secondEnd来存储第二和三个数字的开始位置和截止位置、然后用thirdStart、thirdEnd来验证