【6】连续序列和为s
2024-10-17 08:52:53
题目:输入一个整数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;
}
最新文章
- xcode升级导致git无法使用
- linux常用命令-文件搜索命令-find
- mac终端terminal快捷键:
- Opensource开源精神
- angularjs中ng-change使用方法
- NGUI 便捷的显示与隐藏界面
- 常用的CSSreset整理
- php常用代码(一)
- 250. Count Univalue Subtrees
- 10.10_魔兽账号,OSC代码托管演示,研究SQL别忘记了,git
- 今天给大家分享一下Android中的资源与国际化的问题
- 高效算法——Most financial institutions 贪心 H
- mysql分库分表总结<;转>;
- 理解ROS的参数
- PHP ckeditor富文本编辑器 结合ckfinder实现图片上传功能
- SD卡初始化以及命令详解
- 20175209 《Java程序设计》第七周学习总结
- D - WE POJ - 3273 (二分法)
- 背水一战 Windows 10 (108) - 通知(Tile): application tile 基础, secondary tile 基础
- 【转】HTTP协议—— 简单认识TCP/IP协议