学步园

和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

分析：这是网易的一道面试题。

--------------------------------------

解法一：

既然是连续的，我们当然可以借助两个游标，分别记住起始点和终止点，另一个变量记录和sum，判断sum与n的关系，分别移动游标即可。

下面给出来借助数组记录和游标记录（推荐，节省空间）这个方法的时间复杂度O(n)其实就是循环两次一半的数组

//============================================================================
// Name        : ContinueSum.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

void ContinueSum(int dst);
void ContinueSum2(int dst);

int main() {
	int input;
	cin>>input;
	ContinueSum2(input);

	return 0;
}

/*
 * 借助数组
 */
void ContinueSum(int dst){
	int i=0, j=0;
	int sum = 0;
	int mid = dst/2 + 1;
	int *arr = new int[mid];

	while(i<=mid){
		if(sum <= dst){
			// ==
			if(sum == dst)
				cout<<arr[j]<<"-"<<arr[i-1]<<endl;
			if(i>=mid)
				break;
			arr[i] = ++i;
			sum += arr[i-1];
		}
		else if(sum>dst)
			sum -= arr[j++];
	}

	delete []arr;
}

/*
 * 直接利用游标作为数值记录
 */
void ContinueSum2(int dst){
	int i=0, j=0;
	int sum = 0;
	int mid = dst/2 + 1;

	while(i<=mid){
		if(sum <= dst){
			if(sum == dst)
				cout<<j+1<<"-"<<i<<endl;
			if(i>=mid)
				break;
			sum += ++i;
		}
		else if(sum>dst)
			sum -= ++j;
	}

}

输出如下：

15
1-5
4-6
7-8

解法二：运用数字间关系

我们用手算算，利用求和公式，可以得出起始点和连续个数的关系，利用这个关系可以快速求出答案，而且时间上和上述算法差不多

解题思路如上，这里只需要借助化简后的公式和K的范围，就可以求出来了。。

说明下，如果k=0，得到的答案就是n本身，貌似这题至少要两个连续数，所以就没考虑来