小景哥哥

世界很大,而我们还需要再成长!

您现在的位置是:首页>爱编程>详细内容

41.和为S的连续正数序列

发布时间:2018-08-24 00:00:00编辑:Jason浏览(365)评论(0)

    41.和为S的连续正数序列

    题目描述

    小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
    输出描述:
    输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

     


    import java.util.ArrayList;
    public class Solution {
        public ArrayList<ArrayList<Integer> > FindContinuousSequence1(int sum) {
            ArrayList<ArrayList<Integer>> alllist = new ArrayList<ArrayList<Integer>>();
           if(sum < 3)
               return alllist;
            int small = 1;
            int big = 2;
            int middle = (1 + sum) / 2;
            int curSum = small + big;
            while(small < middle){
                if(curSum == sum){
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    for(int i = small; i <= big; i++)
                        list.add(i);
                    alllist.add(list);
                }
                while(curSum > sum && small < middle){
                    curSum -= small;
                    small++;
                    if(curSum == sum){
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        for(int i = small; i <= big; i++)
                            list.add(i);
                        alllist.add(list);
                    }
                }
                big++;
                curSum += big;
            }
            return alllist;
        }

    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
            ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
            for (int n = (int) Math.sqrt(2 * sum); n >= 2; n--) {
                if ((n & 1) == 1 && sum % n == 0 || (sum % n) * 2 == n) {
                    ArrayList<Integer> list = new ArrayList<>();
                    for (int j = 0, k = (sum / n) - (n - 1) / 2; j < n; j++, k++) {
                        list.add(k);
                    }
                    ans.add(list);
                }
            }
            return ans;
        }
    }

     

关键字词:offer