和为S的连续正数序列-蒲公英云

和为S的连续正数序列

末蓝、 2022-01-31 20:39 307阅读 0赞

题目描述

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

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

主要用到了二分法的思想，思路如下：

import java.util.ArrayList;
public class FindContinuousSequence {
    ArrayList<ArrayList<Integer>> array=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindContinuousSequence1(int sum) {
        int index=sum/2+1;
        for(int i=1;i<=index;i++)
        {
            int right=index;
            int left=i;
            while(left<right && right<=index)
            {
                int mid=(int) Math.ceil((left+right)/2.0);
                int result=(int)((i+mid)/2.0*(mid-i+1));
                if(result==sum)
                {
                    ArrayList<Integer> temp=new ArrayList<>();
                    for(int j=i;j<=mid;j++)
                    {
                        temp.add(j);
                    }
                    array.add(temp);
                    break;
                }
                else if (result>sum)
                {
                    right=mid-1;
                }
                else
                {
                    left=mid+1;
                }
            }
        }
        return array;
    }
    public static void main(String[] args) {
        new FindContinuousSequence().FindContinuousSequence1(3);
    }
}