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

一个有效的累加序列必须至少包含 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
进阶:
你如何处理一个溢出的过大的整数输入?

 

思路：

本题的难点就是确定前两个数  由于至少有三个数  所以第一个数的长度最大只能为length/2 

第二个数从第一个数后面开始，第三个数从第二个数后面开始，我们首先知道，第三个数肯定至少和第一个数与第二个数
一样大，因为是和嘛，若第二个数从i开始到j-1结束，那么第三个数长度最大为L-j，这个长度一定大于等于第一个数和第二个数长度的较大者，即：L-j>=i && L-j>=j-i。 
确定了第二个数的范围之后问题就简单了，看看能不能构成加法序列，只要判断剩下的字串是不是以sum开头即可，然后递归判定

 public boolean isAdditiveNumber(String num) {
		     int len = num.length();
	        //确定第一个数，最终用num.subStr(0,i)来确定第一个数，所以i可以用来标示第一个数的长度，
	        //但是下标i不包含在第一个数中
	        for(int i=1;i<=len/2;i++){
	            //如果长度大于等于2，则不能以0开头
	            if(num.startsWith("0") && i>=2) break;

	            //确定第二个数，第一个数用num.subStr(i,j),包括i，不包括j，所以长度为j-i,
	            //第三个数从下标j开始，长度最长为L-1-j+1，即L-j
	            for(int j=i+1;(len-j)>=i && (len-j)>=j-i;j++){
	                if(num.charAt(i)=='0' && j-i>=2) break;

	                long num1 = Long.parseLong(num.substring(0,i));
	                long num2 = Long.parseLong(num.substring(i,j));

	                if(isValid(num.substring(j), num1, num2)){
	                    return true;
	                }
	            }
	        }
	        return false;
	    }

	    //判断由num1,num2和后续的字串能否构成加法序列
	    public boolean isValid(String remain,long num1,long num2){

	        if(remain.equals("")) return true; //没有剩下的了
	        long sum = num1+num2;

	        String sumStr = ""+sum;
	        if(!remain.startsWith(sumStr)) return false;
	        return isValid(remain.substring(sumStr.length()), num2, sum);
	    }