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

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

 

 

思路：

就简单的方法就是两重循环，

算这两个标志之间的和！

 

代码：

public static int sum(int begin, int end) {
		return ((end - begin + 1) * (begin + end)) / 2;
	}

	public static void find(int number) {
		for (int i = 1; i < number; i++) {
			for (int j = i + 1; j < number; j++) {
				if (sum(i, j) == number) {
					System.out.println("From " + i + " to " + j);
				}
			}
		}
	}

 

 

但是很明显，这个方法每次要重复算的！

算1-3的和其实暗含多算一次1-2！

 

以15为例子，

我们最多算到8！

因为再往后，任意连续的两个数的和都大于15！

 

我们使用sum保持当前计算的数的和，并跟进sum和number的大小来改变其数值和进行相关的入队和出队！

像找15，

那么

1入队，和为1<15，那么继续入队

2入队，和为3<15，继续入队

。

。

。

直到5入队，和为15=15，那么输出对头标志和队尾标志，表面之间的数相加等于所要求的数，然后出队，并让sum减去对头，sum此时为14，则继续入队

6入队，和为20>15，那么出队，减去队头2，sum为为18>15，则继续出队，减去队头3，sum为15=15，符合条件，则出队，减去队头~

重复上诉操作，直到进队的数等于结束的数或者sum<15！

 

代码：

 

int number = 15;
		int end = (number+1)/2;
		System.out.println(end);
		int[] queue = new int[number];
		int head = 0;
		int tail = 0;
		int index = 1;
		int sum = 0;
		do {
			if (sum < number) {
				queue[tail++] = index;
				sum += index;
				System.out.println(index + ":" + sum);
				index++;
			}
			if (sum == number) {
				System.out.println("From " + (head + 1) + " to " + tail);
				sum -= queue[head];
				head++;
			} else if (sum > number) {
				sum -= queue[head];
				head++;
				if (sum == number) {
					System.out.println("From " + (head + 1) + " to " + tail);
					sum -= queue[head];
					head++;
				}
			}
		} while (index <= end || sum > number);