306. 累加数（JS实现）

比眉伴天荒 2022-11-27 15:58 113阅读 0赞

## 1 题目 ##

> 累加数是一个字符串，组成它的数字可以形成累加序列。  
> 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。  
> 给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。  
> 说明: 累加序列里的数不会以 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

链接：https://leetcode-cn.com/problems/additive-number

## 2 思路 ##

**这道题用递归的方法，依次回溯累加即可，比较讨厌的是，要注意处理0的情况，递归函数`d(i,j,k,s)`，其中`i`为指向当前第一个数的开头字符，`j`指向第二个数的开头字符，`k`为第三个数的开头字符**

## 3代码 ##

/** * @param {string} num * @return {boolean} */
    var isAdditiveNumber = function(num) { 
        if (num.length < 3) return false;
    
        let i=0;
        for (let j=i+1; j<num.length-1;j++) { 
            for (let k=j+1; k<num.length; k++) { 
                if (d(i,j,k,num)) return true;
            }
        }
    
        return false;
    
    
        function d(i,j,k,s) { 
            if (k === s.length) return true;
            if (s[i] === '0' && j > i + 1) return false;  //第一个数字不是0，但以0开头
            if (s[j] === '0' && k > j + 1) return false;  //第二个数字不是0，但以0开头
            let num1 = parseInt(s.slice(i,j));
            let num2 = parseInt(s.slice(j,k));
    
            for (let m=k+1; m<=s.length; m++) { 
                if (s[k] === '0' && m > k+1) return false;  //第三个数字不是0，但以0开头
                let num3 = parseInt(s.slice(k,m));
                if (num1 + num2 === num3) { 
                    return d(j,k,m,s);
                } else if (num1 + num2 < num3) {     //若前两个数已经小于第三个数，则提前结束
                    return false;
                }
            }
    
            return false;
        }
    };