本文共 2208 字，大约阅读时间需要 7 分钟。

题目描述

输入一个整数s，打印出所有何为s的连续整数序列(至少含有两个数字）。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。例如输入15，则有3个序列：1，2，3，4，5；4，5，6；7，8。

分析

参考之前的问题：，使用了前后索引。类似的，在本题中使用序列的前后数字（第一个firstNum和最后一个lastNum）。由前后数字可以确定整个连续整数序列及其和tmpSum。如果tmpSum大于s，则从序列中去掉较小值，即增大firstNum的值；如果tmpSum小于s，则从序列中增加最后一个值lastNum，让序列包含更多的数字。由于序列最好都要包含两个数字，一直增加大firstNum到（1+s)/2为止。

牛客AC：

package com.problem;import java.util.ArrayList;import java.util.Iterator;public class ContinuousSeqOfSum {
       /**     * 输入15,输出3个序列：     * 1,2,3,4,5     * 4,5,6，     * 7,8     */    public static void main(String[] args) {        ContinuousSeqOfSum continuousSeqOfSum = new ContinuousSeqOfSum();        int sum = 15;        ArrayList
   
    
     > listAll = continuousSeqOfSum.FindContinuousSequence(sum);        // 遍历打印输出        Iterator
     
      
       > iteratorOuter = listAll.iterator();        while(iteratorOuter.hasNext()) {            Iterator
       
         iteratorInner = iteratorOuter.next().iterator();            while(iteratorInner.hasNext())                System.out.printf("%4d", iteratorInner.next());            System.out.println();        }    }    public ArrayList
        
         
          > FindContinuousSequence(int sum) { ArrayList
          
           
            > listAll = new ArrayList
            
             
              >(); int firstNum = 1; // 第一个数 int lastNum = 2; // 最后一个数 int midNum = (1 + sum) / 2; // 中间的数 int tmpSum = firstNum + lastNum; // 初始和 // 序列至少有两个数，循环条件为第一个数一直增加到midNum,即(1+sum)/2为止 while(firstNum < midNum) { // 和相等，则找到序列的起始值和终止值，加入到序列 if(tmpSum == sum) { ArrayList
              
                list = addSeqToList(firstNum, lastNum); listAll.add(list); } // 和大于sum，并且第一个数尚未增加到midNum // 将第一个数（序列中最小的数去除，则最小的数更新的下一个数），在进行判断 // 直到和小于sum或者第一个数增加到midNum，退出循环 while(tmpSum > sum && firstNum < midNum) { tmpSum -= firstNum; firstNum++; if(tmpSum == sum) { ArrayList
               
                 list = addSeqToList(firstNum, lastNum); listAll.add(list); } } // 和小于sum，将最后一个数增加1，计算新的和 lastNum++; tmpSum += lastNum; } return listAll; } /** * 将起始值和结束值及其之间的连续序列加入list * @param firstNum * @param lastNum * @return */ public ArrayList
                
                  addSeqToList(int firstNum, int lastNum) { ArrayList
                 
                   list = new ArrayList
                  
                   (); if(firstNum > lastNum) return list; for(int i = firstNum; i <= lastNum; i++) list.add(i); return list; }}
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

参考

转载地址：http://qzxgi.baihongyu.com/