0306. 累加数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举 + 大数加法

1. 📝 题目描述

• leetcode

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

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

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

2. 🎯 s.1 - 枚举 + 大数加法

c

char* addStrings(const char* a, const char* b) {
    int la = strlen(a), lb = strlen(b);
    int maxLen = (la > lb ? la : lb) + 2;
    char* res = (char*)calloc(maxLen, 1);
    int i = la - 1, j = lb - 1, k = maxLen - 2, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res[k--] = sum % 10 + '0';
        carry = sum / 10;
    }
    return res + k + 1;
}

bool isAdditiveNumber(char* num) {
    int n = strlen(num);
    for (int i = 1; i <= n / 2; i++) {
        for (int j = i + 1; j < n; j++) {
            if (i > 1 && num[0] == '0') break;
            if (j - i > 1 && num[i] == '0') continue;
            char s1[n + 1], s2[n + 1];
            strncpy(s1, num, i); s1[i] = '\0';
            strncpy(s2, num + i, j - i); s2[j - i] = '\0';
            char *a = strdup(s1), *b = strdup(s2);
            int pos = j;
            while (pos < n) {
                char* c = addStrings(a, b);
                int cl = strlen(c);
                if (strncmp(num + pos, c, cl) != 0) break;
                pos += cl;
                a = b;
                b = c;
            }
            if (pos == n) return true;
        }
    }
    return false;
}

js

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
  const n = num.length
  function addStrings(a, b) {
    let i = a.length - 1,
      j = b.length - 1,
      carry = 0,
      res = ''
    while (i >= 0 || j >= 0 || carry) {
      const sum = (i >= 0 ? +a[i--] : 0) + (j >= 0 ? +b[j--] : 0) + carry
      res = (sum % 10) + res
      carry = Math.floor(sum / 10)
    }
    return res
  }
  for (let i = 1; i <= Math.floor(n / 2); i++) {
    for (let j = i + 1; j < n; j++) {
      const s1 = num.slice(0, i),
        s2 = num.slice(i, j)
      if (s1.length > 1 && s1[0] === '0') break
      if (s2.length > 1 && s2[0] === '0') continue
      let a = s1,
        b = s2,
        pos = j
      while (pos < n) {
        const c = addStrings(a, b)
        if (!num.startsWith(c, pos)) break
        pos += c.length
        a = b
        b = c
      }
      if (pos === n) return true
    }
  }
  return false
}

py

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for i in range(1, n // 2 + 1):
            for j in range(i + 1, n):
                s1, s2 = num[:i], num[i:j]
                if len(s1) > 1 and s1[0] == '0':
                    break
                if len(s2) > 1 and s2[0] == '0':
                    continue
                a, b, pos = s1, s2, j
                while pos < n:
                    c = str(int(a) + int(b))
                    if not num.startswith(c, pos):
                        break
                    pos += len(c)
                    a, b = b, c
                if pos == n:
                    return True
        return False

• 时间复杂度：$O(n^3)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(n)$，存储中间字符串

算法思路：

• 枚举前两个数的分割位置，然后不断验证后续是否满足累加关系
• 使用字符串加法避免大数溢出，注意跳过前导零