和为n连续正数序列 【微软面试100题 第五十一题】 - tractorman - 博客园

和为n连续正数序列 【微软面试100题 第五十一题】 - tractorman - 博客园
　　输入一个正数n，输出所有和为n连续正数序列（至少两个）。
　　例如输入15，由于1+2+3+4+5 = 4+5+6 = 7+8 = 15.所以输出3个连续序列1~5,4~6,7~8.

　　可以用两个变量small和big表示一个区间small~big，再用一个变量sum表示这个区间的数的和如果sum>n,则small向后移，如果sum<n则big向后移，如果sum=n则输出该区间small~big.

void FindContinuousSequence(int n)
{
    //因为至少两个正数，1+2=3，因此如果n<3则不存在连续序列
    if(n<3)
        return;
    int small = 1;
    int big = 2;
    //至少两个数，则最小的数肯定小于mid，作为退出while条件
    int mid = (1+n)/2;
    int curSum = small+big;
    while(small<mid)
    {
        if(curSum==n)
            Print(small,big);
        while(curSum>n && small<mid)
        {
            curSum -= small;
            small++;
            if(curSum==n)
                Print(small,big);
        }
        big++;
        curSum += big;
    }
}

https://blog.csdn.net/hopestar2/article/details/4645812
   方法1. 使用枚举的方法，两个for循环可以搞定。时间复杂度O(n^2)

   方法2. 因为整数序列是有序的，可以设立两个游标small,big，通过判区间[small,big]的和是

否为N来得到这个序列。如果区间和大于n,small往前移动，如果小于n,big往前移动，等于就输出

这个区间。时间复杂度是0(n).
   方法3. 假设 a + (a+1) + ... + b = n 是一个答案，则根据求和公式就是 (a + b) * (b - a

+ 1) / 2 = n, 则 (a+b)和 (b-a+1)分别是2N的一个因子，枚举其中一个，就可以判断求出第二个，

然后求出a和b了。时间复杂度是O(sqrt(n)).2n的因子范围肯定在[2,sqrt(2n)]之间。

   具体步骤：假设（b-a+1)是其中一个因子，可以通过2n%i == 0找到一个因子i,然后根据上面的

（a+b)*(b-a+1)/2 = n的公式可以推导出 2*a*i = 2n - i^2 + i, 因此只要判断a存在正整数解，就

可以知道满足上面条件的2n的另一个因子也是存在的。

void ContinuousSequenceSum_2(int n)
{
int nMax = (int)sqrt(2*n) + 1;
int start,end,i;
for(i = 2; i < nMax; i++)
{
if(2*n % i == 0)
{ 
int tmp = 2*n - i*i + i;
if(tmp % (2*i) == 0)
{
start = tmp / (2*i);
end = start + i -1;
printf("start = %d, end = %d/n", start, end);
}
}
}
}
https://to-zoe-yang.iteye.com/blog/1174421
https://www.cnblogs.com/python27/archive/2011/12/04/2275605.html

　　容易看出，这种算法需要遍历的范围是从２—sqrt(2n)，因而时间复杂度为O(sqrt(n))，效率还算是比较高的，然而缺点是要计算很多的乘除，乘方运算，对于n值较大输入，计算过程会相对较慢。

【思路1】从等差数列的观点考虑：如果有一列数满足i+(i+1)+...+j=n,根据等差数列的求和公式，我们容易得到：(i+j)(j-i+1)/2=n,即(i+j)(j-i+1)=2n,由于i，j均为正整数，我们容易得到(i+j),(j-i+1)也都为正整数，所以都是2n的因子，我们就可以从2到sqrt（2n）遍历2n的所有因子，对于其中的因子k，我们有：

　　我们只需要保证j，i的值都为整数，并且i<ｊ即可。根据这种思路我们有如下的代码：

 6 void FindContinuousSequence(int n)
 7 {
 8     int half = (int)(sqrt(2*n));
 9     for(int k = 2;k <= half;++k)
10     {
11         //找到因子k
12         if((2*n) % k == 0)
13         {
14             int temp1 = 2 * n - k*k + k;
15             int temp2 = 2 * n + k*k - k;
16 
17             //开始数start，结束数end都为整数
18             if(temp1 % (2*k) == 0 && temp2 % (2*k) == 0)
19             {
20                 int start = temp1 / (2*k);
21                 int end = temp2 / (2*k);
22 
23                 //打印从start到end之间的所有数
24                 for(int i = start;i <= end;++i)
25                     cout<<i<<"\t";
26                 
27                 cout<<endl;
28             }
29         }
30     }
31 }

https://www.jianshu.com/p/cd7cc204809b?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation
Read full article from 和为n连续正数序列 【微软面试100题 第五十一题】 - tractorman - 博客园