Go Java算法之累加数示例详解

什么是累加数

累加数是指一个字符串序列，划分成多个数字序列，每个数字序列的数字之和等于后面的数字序列的第一个数字。

例如：112358 是一个累加数，因为 1+1=2, 1+2=3, 2+3=5, 3+5=8，后面的数字序列分别为 1, 2, 3, 5。

算法思路

为了判断一个字符串是否为累加数，我们需要枚举前两个数字，然后依次判断后面的数字序列是否合法即可。

假设第一个数字为 i，第二个数字为 j，那么第三个数字就是 i+j，接下来用 i+j 对原字符串进行截取，判断剩余的字符串是否为 i+j，以此类推。

注意，数字序列不能以 0 开头，所以 i 和 j 可能是一位数、两位数、三位数中的任意两个数字。

示例说明

下面给出两个示例，来详细解释累加数的判断过程。

示例一

输入的字符串为 "11235813"。

我们首先枚举前两个数字：i=1, j=1。

然后计算出第三个数字，即 i+j=2，将字符串从当前位置截取出来，得到 "235813"，判断该字符串是否为 2，发现不是，因此这个枚举的结果不合法。

接下来我们枚举下一组：i=1, j=2。

计算出第三个数字 i+j=3，截取字符串得到 "35813"，判断该字符串是否为 3，不是。

接下来继续枚举：i=2, j=3。

计算出第三个数字 i+j=5，截取字符串得到 "5813"，判断该字符串是否为 5，不是。

接下来继续枚举：i=3, j=5。

计算出第三个数字 i+j=8，截取字符串得到 "13"，判断该字符串是否为 8，不是。

接下来继续枚举：i=5, j=8。

计算出第三个数字 i+j=13，截取字符串得到 ""，判断该字符串是否为 13，是。

因此，该字符串是一个累加数。

示例二

输入的字符串为 "199100199"。

我们首先枚举前两个数字：i=1, j=9。

然后计算出第三个数字，即 i+j=10，由于下一位是 9，因此第一部分为 "19"。

依次计算出第四个数字：i+j=19，截取字符串得到 "9100199"，发现它不等于 19，因此这个枚举的结果不合法。

接下来继续枚举：i=9, j=1。

计算出第三个数字 i+j=10，由于第二部分以 0 开头，不合法。

接下来继续枚举：i=1, j=9。

计算出第三个数字 i+j=10，第一部分为 "19"，第二部分为 "9"。

依次计算出第四个数字：i+j=19，截取字符串得到 "100199"，不等于 19。

接下来继续枚举：i=9, j=1。

计算出第三个数字 i+j=10，第一部分为 "199"，第二部分为 "1"。

依次计算出第四个数字：i+j=11，截取字符串得到 "00199"，不等于 11。

接下来继续枚举：i=1, j=9。

计算出第三个数字 i+j=10，第一部分为 "1"，第二部分为 "99100199"。

依次计算出第四个数字：i+j=9，截取字符串得到 "9100199"，不等于 9。

接下来继续枚举：i=9, j=9。

由于第一个数字不能为 0，因此这个枚举的结果不合法。

因此，该字符串不是一个累加数。

代码实现

下面给出代码实现的主要部分，具体实现细节请参考代码注释。

func isAdditiveNumber(num string) bool {
    n := len(num)
    for i := 1; i <= n/2; i++ { // 枚举第一个数字的长度
        for j := 1; j <= (n-i)/2; j++ { // 枚举第二个数字的长度
            if check(num[:i], num[i:i+j], num[i+j:]) { // 如果找到了一个累加数直接返回 true
                return true
            }
            // 如果第二个数字以 0 开头，则不能继续往下枚举
            if num[i:i+j][0] == '0' {
                break
            }
        }
        // 如果第一个数字以 0 开头，则不能继续往下枚举
        if num[0] == '0' {
            break
        }
    }
    return false
}

// 判断是否为累加数
func check(s1, s2, s3 string) bool {
    for len(s3) > 0 { // 按照累加数的定义依次判断后面的数字序列
        if !strings.HasPrefix(s3, add(s1, s2)) {
            return false
        }
        s1, s2, s3 = s2, add(s1, s2), s3[len(add(s1, s2)):]
    }
    return true
}

// 计算两个字符串数字的和
func add(s1, s2 string) string {
    i, j, carry, sum := len(s1)-1, len(s2)-1, 0, []byte{}
    for i >= 0 || j >= 0 {
        n1, n2 := 0, 0
        if i >= 0 {
            n1 = int(s1[i] - '0')
            i--
        }
        if j >= 0 {
            n2 = int(s2[j] - '0')
            j--
        }
        tmp := n1 + n2 + carry
        sum = append(sum, byte(tmp%10)+'0')
        carry = tmp / 10
    }
    if carry > 0 {
        sum = append(sum, byte(carry)+'0')
    }
    // 由于我们计算结果时是从低位开始的，因此要将结果翻转一下
    for i, n := 0, len(sum); i < n/2; i++ {
        sum[i], sum[n-i-1] = sum[n-i-1], sum[i]
    }
    return string(sum)
}

总结

累加数问题实际上可以转化为一个回溯问题，但是优化后的暴力枚举已经足够应对该问题。在实现时需要注意细节，例如数字序列不能以 0 开头、要注意截取字符串的范围等等。