【面试题】输入一个正数，打印出所有和正数的连续正数序列（至少含有两个数）

90 阅读 0 评论 60 点赞

我是靠谱客的博主尊敬手套，这篇文章主要介绍【面试题】输入一个正数，打印出所有和正数的连续正数序列（至少含有两个数），现在分享给大家，希望可以做个参考。

今天笔试遇到了一道感觉还不错的题目，后面搜索发现好像是网易公司的笔试题，所以就记录一下分享给大家。

题目如下：

输入一个正数target，打印出所有和为target的连续正数序列（至少含有两个数）。例如输入15，由于1＋2＋3＋4＋5＝4＋5＋6＝7＋8＝15，所以结果打印出3个连续序列1～5、4～6和7～8。

个人分析：可以定义两个变量，left 和 right，最开始让 left = 1，right = 2；如果 left 加到 right 相加小于 target，证明整体要变大， right 要增大；如果 left 加到 right 大于 target，证明整体要变小，让 left 增大；当相加等于 target 的时候，就得到了一个连续整数序列了，接着 left 继续增大，继续寻找其他序列，其中 left 最大只能是 target÷2。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
int sum(int left, int right)
{
	int total = 0;
	for (int i = left; i <= right; i++)
	{
		total += i;
	}
	return total;
}
int main()
{
	int target;
	int left = 1;
	int right = 2;
	cin >> target;
	if (target < 3)  //因为至少包含两个数（此处默认为两个正数）
	{
		return -1;
	}
	
	while (left <= target / 2)
	{
		if (sum(left,right) < target)
		{
			right++;
		}

		if (sum(left, right) > target)
		{
			left++;
		}

		if (sum(left, right) == target)
		{
			for (int i = left; i <= right; i++)
			{
				cout << i << " ";
			}
			cout << endl;
			left++;
		}

	}

	return 0;
}