首页 > 代码库 > 连续序列和为s

连续序列和为s

题目:输入一个整数s,打印出所有和为s的连续整数序列(至少含有2个数)。例如输入9,则输出2、3、4和4、5两个序列


方案一:由于序列至少要2个数,则两个数上限值为(1+s)/2,我们可以枚举该序列的起点和终点求所有满足的序列。时间复杂度为O(n^2),效率比较低

方案二:我们设置两个指针start和end分别表示当前序列的起点和终点,并记序列和为sum。当sum = s的时候输出这个序列,并且end往后移动一位;如果sum > s,则start往后移动一位;如果sum < s,则end要往后移动一位。

              直到start < (1+s)/2结束循环,时间复杂度O(n),效率很高


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//打印序列
void PrintNum(int start, int end){
	for(int i = start; i <= end; i++){
	    printf("%d ", i);
	}
	printf("\n");
}

//找到两个数和为s
void FindSequenceSum(int s){
	if(s < 3){ //和小于3是不合法的数据
	    return;
	}
	int start = 1;
	int end = 2;
	int sum = 3;
	int mid = (1+s)>>1;
	//循环找到所有的序列
	while(start < mid){ //序列的起点要小于(1+s)的一半
		if(sum == s){ //和为sum的序列直接打印
		    PrintNum(start, end);
		    end++;
		    sum += end;
		}
		else if(sum > s){ //和大于s的序列则起始点往后移动一个
		    sum -= start;
		    start++;
		}
		else{ //和小于s的序列则终点往后移动一位
		    end++; 
		    sum += end;
		}
	}
}

int main(){
	FindSequenceSum(9);
	getchar();
	return 0;
}