306. 累加数

Medium

题目描述

累加数是指其数字可以组成累加序列的字符串。

一个有效的累加序列必须至少包含 3 个数字。除了前两个数字外，序列中的每个后续数字都必须是前面两个数字的和。

给定一个只包含数字的字符串，判断它是否为累加数。如果是，返回 true；否则，返回 false。

注意：累加序列中的数字不能有前导零，所以序列 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"本身）
序列验证：从第三个数开始，逐一验证每个数是否等于前两个数的和
字符串加法：实现大整数字符串相加，处理溢出问题

优化点：

第一个数的长度最多为 n/2（保证至少有三个数）
第二个数的长度最多为 (n-i)/2（其中 i 是第一个数的长度）
使用字符串操作避免整数溢出

时间复杂度主要取决于枚举前两个数的组合数和验证过程，总体较为高效。

代码实现

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.length();
        for (int i = 1; i <= n / 2; i++) {
            for (int j = 1; j <= (n - i) / 2; j++) {
                if (isValid(num, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    
private:
    bool isValid(const string& num, int start, int len1, int len2) {
        string num1 = num.substr(start, len1);
        string num2 = num.substr(start + len1, len2);
        
        if (hasLeadingZero(num1) || hasLeadingZero(num2)) {
            return false;
        }
        
        int pos = start + len1 + len2;
        while (pos < num.length()) {
            string sum = addStrings(num1, num2);
            if (pos + sum.length() > num.length() || 
                num.substr(pos, sum.length()) != sum) {
                return false;
            }
            pos += sum.length();
            num1 = num2;
            num2 = sum;
        }
        return true;
    }
    
    bool hasLeadingZero(const string& s) {
        return s.length() > 1 && s[0] == '0';
    }
    
    string addStrings(const string& num1, const string& num2) {
        string result = "";
        int carry = 0;
        int i = num1.length() - 1, j = num2.length() - 1;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += num1[i--] - '0';
            if (j >= 0) sum += num2[j--] - '0';
            
            result = char(sum % 10 + '0') + result;
            carry = sum / 10;
        }
        return result;
    }
};

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for i in range(1, n // 2 + 1):
            for j in range(1, (n - i) // 2 + 1):
                if self.is_valid(num, 0, i, j):
                    return True
        return False
    
    def is_valid(self, num: str, start: int, len1: int, len2: int) -> bool:
        num1 = num[start:start + len1]
        num2 = num[start + len1:start + len1 + len2]
        
        if self.has_leading_zero(num1) or self.has_leading_zero(num2):
            return False
        
        pos = start + len1 + len2
        while pos < len(num):
            sum_str = str(int(num1) + int(num2))
            if pos + len(sum_str) > len(num) or num[pos:pos + len(sum_str)] != sum_str:
                return False
            pos += len(sum_str)
            num1, num2 = num2, sum_str
        return True
    
    def has_leading_zero(self, s: str) -> bool:
        return len(s) > 1 and s[0] == '0'

public class Solution {
    public bool IsAdditiveNumber(string num) {
        int n = num.Length;
        for (int i = 1; i <= n / 2; i++) {
            for (int j = 1; j <= (n - i) / 2; j++) {
                if (IsValid(num, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private bool IsValid(string num, int start, int len1, int len2) {
        string num1 = num.Substring(start, len1);
        string num2 = num.Substring(start + len1, len2);
        
        if (HasLeadingZero(num1) || HasLeadingZero(num2)) {
            return false;
        }
        
        int pos = start + len1 + len2;
        while (pos < num.Length) {
            string sum = AddStrings(num1, num2);
            if (pos + sum.Length > num.Length || 
                num.Substring(pos, sum.Length) != sum) {
                return false;
            }
            pos += sum.Length;
            num1 = num2;
            num2 = sum;
        }
        return true;
    }
    
    private bool HasLeadingZero(string s) {
        return s.Length > 1 && s[0] == '0';
    }
    
    private string AddStrings(string num1, string num2) {
        var result = new StringBuilder();
        int carry = 0;
        int i = num1.Length - 1, j = num2.Length - 1;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += num1[i--] - '0';
            if (j >= 0) sum += num2[j--] - '0';
            
            result.Insert(0, sum % 10);
            carry = sum / 10;
        }
        return result.ToString();
    }
}

var isAdditiveNumber = function(num) {
    const n = num.length;
    for (let i = 1; i <= Math.floor(n / 2); i++) {
        for (let j = 1; j <= Math.floor((n - i) / 2); j++) {
            if (isValid(num, 0, i, j)) {
                return true;
            }
        }
    }
    return false;
    
    function isValid(num, start, len1, len2) {
        let num1 = num.substring(start, start + len1);
        let num2 = num.substring(start + len1, start + len1 + len2);
        
        if (hasLeadingZero(num1) || hasLeadingZero(num2)) {
            return false;
        }
        
        let pos = start + len1 + len2;
        while (pos < num.length) {
            const sum = (BigInt(num1) + BigInt(num2)).toString();
            if (pos + sum.length > num.length || 
                num.substring(pos, pos + sum.length) !== sum) {
                return false;
            }
            pos += sum.length;
            num1 = num2;
            num2 = sum;
        }
        return true;
    }
    
    function hasLeadingZero(s) {
        return s.length > 1 && s[0]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

解法	时间复杂度	空间复杂度
回溯 + 字符串加法	O(n³)	O(n)

时间复杂度说明：

枚举前两个数的组合：O(n²)
验证序列的过程：O(n)
字符串加法操作：O(n)
总体：O(n³)

空间复杂度说明：

存储临时字符串：O(n)
递归调用栈深度：O(1)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目