面试题57(2):和为s的连续正数序列

题目

输入一个正数s，打印出所有和为s的连续正数序列(至少含有两个数)。例如。输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3个连续序列1_5、46和7~8。

解题思路

1. 考虑两个数small和big分别表示序列的最小值和最大值。
2. 首先把small初始化为1，big初始化为2。
3. 如果small到big的序列的和大于s，则从序列中去掉较小的值，也就是增加small的值
4. 如果从small到big的序列的和小于s,则可以增大big
5. 终止条件时small增加到(1+s)/2为止

代码

• 细节
  以求和为9的所有连续序列为例
  1)先把small初始化为1，big初始化为2.此时介于small和big之间的序列是{1,2}，序列的和为3<9,所以应让序列包含更多的数字

2. 让big增加1变成3，此时序列为{1,2,3}。序列的和为6<9，继续增加big，序列变为{1,2,3,4}，序列的和为10>9
3. 删除序列中的一些数字，让small递增，此时序列为{2,3,4}，序列的和刚好等于9.第一个连续数字的序列找到了
   4)接着增加big,重复前面的过程。

class Solution{
    public:
        void printConSequence(int small,int big)
        {
            for(int i = small;i<=big;i++)
            {
                cout << i << " ";
            }
            cout << endl;
        }
        
        void findConSequence(int sum)
        {
            if(sum < 3)
            {
                return ;
            }
            int small = 1;
            int big = 2;
            int middle = (1+sum)/2;
            int curSum = small +big;
            while(small < middle)
            {
                if(curSum == sum)
                {
                    printConSequence(small,big);
                }
                
                while(curSum > sum && small < middle)
                {
                    curSum-=small;
                    small++;
                    if(curSum == sum)
                    {
                        printConSequence(small,big);
                    }
                }

                big++;
                curSum +=big;
            }

        }
};

完整代码见Github