题解 | #累加序列#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr string字符串
     * @return bool布尔型
     */
    string solve(string s, string t) {
        int m = t.size();
        int n = s.size();
        int z;  // 获取二者之间的最大长度
        if (m > n) {
            // 在短字符串前补充0
            s = string(m - n, '0') + s;
            z = m;
        } else {
            if (m < n) {
                // 在短字符串前补充0
                t = string(n - m, '0') + t;
                z = n;
            } else {
                z = m;
            }
        }
        string out;
        int c = 0;  // 进位
        // 从最右的低位开始相加
        for (int i = z - 1; i >= 0; i--) {
            int a = s[i] - '0';
            int b = t[i] - '0';
            int d = (a + b + c) % 10;
            c = (a + b + c) / 10;
            char ch = '0' + d;
            out = ch + out;
        }
        // c为1，最高位需要进位
        if (c) {
            char ch = '0' + c;
            out = ch + out;
        }
        return out;
    }

    bool test(string s, int i, int j, int k) {
        string s1 = s.substr(i, j - i);
        string s2 = s.substr(j, k - j);
        if(s1[0] == '0' || s2[0] == '0')
            return false;
//    unsigned long long  i1 = stoull(s1);
//    unsigned long long  i2 = stoull(s2);
//    unsigned long long  sum = i1 + i2;
//    string s3 = to_string(sum);
        string s3 = solve(s1, s2);
        int n = s3.length();
        if (s3 == s.substr(k, n)) {
            if (k + n >= s.length())
                return true;
            return test(s, j, k, k + n);
        }
        return false;
    }
    bool AdditiveArray(string arr) {
        // write code here
        bool flag = false;
        int n = arr.length();
        int len = 0;
        if (n % 2 == 1) {
            len = n / 2;
        } else {
            len = n / 2 - 1;
        }
        for (int i = 1; i <= len; ++i) {
            for (int j = 1; (i + j) < arr.length(); ++j) {
                if (test(arr, 0, i, i + j)) {
                    return true;
                }
            }
        }
        return flag;
    }
};