题解 | #和为S的连续正数序列#
和为S的连续正数序列
http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
直接暴力遍历
1.每次找到从当前数开始累积,累积到目标值,就把这一路序列加入结果路径,停止此次遍历;如果累积不到,那么第一次大于目标值的时候,就停止;
2.从下一个数开始继续尝试累积。。。
3.优化的话,可以在某次累积遍历到目标值的一半+1的时候就停止新的累积尝试
import java.util.ArrayList; public class Solution { static ArrayList<ArrayList<Integer>> res=new ArrayList(); public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { for(int i=1;i<=sum;i++){ if(i>=sum/2+1)break; int mysum=0; mysum+=i; ArrayList<Integer> now=new ArrayList(); now.add(i); for(int j=i+1;j<=sum;j++){ mysum+=j; now.add(j); if(mysum==sum){ res.add(now); break; } if(mysum>sum){ break; } } } return res; } }