题解 | #和为S的连续正数序列#
和为S的连续正数序列
http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
思路:
1.设置一个起始值命名为start,start从1开始
2.从start开始一直往后加,和由value存储。
1)若value小于sum,则继续加。
2)若value=sum,把start到i之间的所有值加入到list中,最后把list加入到返回的res中。
3)若value>sum,直接退出,重新开始,并使sart+1,重新开始。
注意:由于组成sum的值至少由2个数组成,且sum/2+sum/2+1>=sum。因此start<=sum/2。这将作为外层循环的终止条件。
import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> res=new ArrayList<>();//返回列表 int start=1;//起始值 while(start<=sum/2){//当起始值小于等于sum/2,可继续执行。一旦超过sum/2,即使只有两个数相加也会大于sum。 int value=0;//暂时存储当前遍历的数的和 int i=start;//保存start while(value<=sum){//当前和小于等于sum可执行,否则直接退出。 if(value==sum){//符合条件则加入list ArrayList<Integer> list=new ArrayList<>(); for(int j=start;j<i;j++){ list.add(j); } //将list加入到最终返回的列表 res.add(list); break;//退出循环,开始下一轮的寻找。 }else{//不满足条件,继续向后寻找 value+=i; i++; } } start++; } return res; } }