和为S的连续正整数
和为S的连续正数序列
http://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
感觉不知道怎么回事,想着想着就往递归的方向去做了:
首先题目要求至少两个连续的数的和为指定值,因此如果是两个数的话,
必定是1+sum/2 和 sum/2,因此普遍情况(两个数字及以上)一定小于等于 1+sum/2
因此使用一个递归公式,当数字和满足的情况下才进行添加,由于是从最后一个数添加的,那么根据题意还需要排个序
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
for(int i = 1;i<=1+sum/2;i++){
ArrayList<Integer> list = new ArrayList<>();
boolean flag= callBack(i, 0, sum, list);
if (flag && list.size()>0){
list.add(i);
Collections.sort(list);
lists.add(list);
}
}
return lists;
}
public boolean callBack(int count,int ourTotal,int sum, ArrayList<Integer> list ){
ourTotal = ourTotal + count;
if(sum == ourTotal){
return true;
}else if(ourTotal > sum){
return false;
}else {
boolean flag = callBack(count+1,ourTotal,sum,list);
if(flag){
list.add(count+1);
}
return flag;
}
}
}