打印和为N的连续正整数序列

78 阅读 0 评论 52 点赞

我是靠谱客的博主超帅睫毛，最近开发中收集的这篇文章主要介绍打印和为N的连续正整数序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

输入一个正数 n，输出所有和为 n 连续正数序列

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6 和 7-8。

第一种方法：

import java.util.ArrayList;
/*
 * 用等差数列求和公式解决
 * 因为是和为n的连续正整数序列
 * 等差数列求和公式可以求到：和为n的连续序列的第一个数，最后一个数，以及数的个数。
 * s=(a1+an)*n/2   2*s=(a1+an)*n   n=an-a1+1
 */
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum){
       ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
       
        if(sum<=2)
           return list;
       else{
         boolean isExist = false;
         int a1;
         int an;
         int n;
         int num=sum;
         
    //第一个数 ，假如第一个数已经到了num的一半 后面的数初始是第一个数加1，加起来和已经超过num 
    //因此第一个数最大不超过num/2  假如num是奇数 如num=15 15/2=7 ，7仍小于num/2 因此要num/2+1
         for(a1=1;a1<num/2+1;a1++){
            //第二个数
             for(an=a1+1;an<num;an++){
                 if(a1+an>num)
                     break;
                 //两数之间数字的个数
                 n=an-a1+1;
                 //满足条件
                 if((a1+an)*n==2*num){
                   //ArrayList中存储的是对象的引用，所以每次都需要创建一个新对象，否则值会被覆盖
                     ArrayList<Integer> temp=new ArrayList<>();
                   //  temp.clear();
                     isExist=true;
                     //将满足条件的数打印
                  for(int i=a1;i<=an;i++){
            // 转义字符用双引号引起来
            // t是制表符 ,前边没有输出内容则表示8个空格 有内容则表示加上前面输出的内容共占8个空格
            // print()表示下一次打印不换行        println()表示下次打印换行
                    //  System.out.print(i+"t");
                      temp.add(i);
                     }
                     //将所有满足条件的组合放入list中
                     list.add(temp);
                      
                    // System.out.println();
                     break;
                 }
                  
             }
         }
         return list;
       }
       
   }
    
}

第二种方法：

我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为 1，big初始化为 2。如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2，因为序列至少要有两个数字。

import java.util.ArrayList;
/*
*初始化small=1，big=2;
*small到big序列和小于sum，big++;大于sum，small++;
*当small增加到(1+sum)/2是停止
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        if(sum<=1){return lists;}
        int small=1;
        int big=2;
        while(small!=(1+sum)/2){          //当small==(1+sum)/2的时候停止
            int curSum=sumOfList(small,big);
            if(curSum==sum){
                ArrayList<Integer> list=new ArrayList<Integer>();
                for(int i=small;i<=big;i++){
                    list.add(i);
                }
                lists.add(list);
                small++;big++;
            }else if(curSum<sum){
                big++;
            }else{
                small++;
            }
        }
        return lists;
    }
     
    public int sumOfList(int head,int leap){        //计算当前序列的和
        int sum=head;
        for(int i=head+1;i<=leap;i++){
            sum+=i;
        }
        return sum;
    }
}