题解68 | #累加序列#

class Solution {
  public:
    bool AdditiveArray(string arr) {
        int n = arr.size();
        for (int i = 1; i <= n / 2; i++) {
            for (int j = 1; j <= (n - i) / 2; j++) {
                if (isValid(arr, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool isValid(string arr, int i, int j) {
        if (arr[0] == '0' && i > 1) return false;
        if (arr[i] == '0' && j > 1) return false;

        string num1 = arr.substr(0, i);
        string num2 = arr.substr(i, j);

        int k = i + j;
        while (k < arr.size()) {
            string sum = addStrings(num1, num2);
            if (k + sum.size() > arr.size() || arr.substr(k, sum.size()) != sum) {
                return false;
            }
            num1 = num2;
            num2 = sum;
            k += sum.size();
        }

        return true;
    }

    string addStrings(string num1, string num2) {
        string res;
        int carry = 0;
        int i = num1.size() - 1, j = num2.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            int x = i >= 0 ? num1[i--] - '0' : 0;
            int y = j >= 0 ? num2[j--] - '0' : 0;
            int sum = x + y + carry;
            res = to_string(sum % 10) + res;
            carry = sum / 10;
        }
        return res;
    }
};

算法的基本思想

使用双重循环来遍历可能的第一个数和第二个数的长度，然后检查剩余的字符串是否满足累加序列的性质。在检查过程中，使用addStrings函数来计算两个字符串形式的数字的和，并使用isValid函数来验证剩余的字符串是否满足累加序列的性质。

时间复杂度分析：

外层循环遍历可能的第一个数的长度，内层循环遍历可能的第二个数的长度，因此时间复杂度为O(n^2)，其中n为字符串的长度。

在isValid函数中，使用了addStrings函数来计算两个字符串的和，addStrings函数的时间复杂度为O(max(m, n))，其中m和n分别为两个字符串的长度。因此，isValid函数的时间复杂度为O(n)。

综合起来，整个算法的时间复杂度为O(n^3)。

空间复杂度分析：

算法使用了常数级别的额外空间来存储变量和结果，因此空间复杂度为O(1)。