【剑指offer】和为S的连续正数序列
2024-08-24 19:32:12
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
分析:采用双指针来确定合法序列的左右边界
当序列值太大的时候,左指针右移
当序列值太小的时候,右指针左移
计算序列的和我们可以通过递增数列的求和公式计算
时间复杂度:O(N)
//双指针法
vector<vector<int> >vv;
vector<int> v;
void f(int x,int y)//将边界x,y的序列放入结果
{
for(int i=x;i<=y;i++)
v.push_back(i);
vv.push_back(v);
v.clear();
}
vector<vector<int> > FindContinuousSequence(int sum)
{
int low,high;
if(sum<3)
return vv;
low=high=1; while(!(low==high&&low==sum/2+1))//注意low的边界,这样可以少算很多
{
int cur=(low+high)*(high-low+1)/2;//求和公式
if(cur==sum)
{
f(low,high);
low++;
}else if(cur<sum)//当前序列值太小,需要变大点,所以右指针右移
{
high++;
}else if(cur>sum)//当前序列值太大,需要变小点,所以左指针右移
{
low++;
}
}
return vv;
}
最新文章
- Flink &ndash; window operator
- 领导让我重新做一个微信H5页面!
- 【BZOJ 4326】【NOIP2015】运输计划
- Qt修改xml文件
- MS 数据库存储过程加密解密
- 第九篇、CSS布局
- Qt 学习之路 :文件
- MYSQL可调用执行自定义SQL的代码
- 适配iOS11
- .NET程序员所需要注意的网站资源
- spark的运行模式
- HTML语言发展史
- 【ARTS】01_15_左耳听风-20190218~20190224
- 怎么将APE转MP3,APE转MP3的方法
- css3 实现图片等比例放大与缩小
- 根据txt中的文件名将文件复制到目标文件夹中
- VMWARE虚拟机不显示主机共享的文件夹解决办法
- html中控制Tab键的顺序
- Sql server bulk insert
- Kconfig详解
热门文章
- 工作拾记 - 关于easyui模板后台改为vue-element
- PHP入门之调试
- 牛客网 牛客练习赛4 A.Laptop-二维偏序+离散化+树状数组
- docker时区问题
- 组合模式( Composite Pattern)
- opencv 图像resize
- Anaconda更新失败简单解决[CondaHTTPError: HTTP 000 CONNECTION FAILED for url]
- Ubuntu 安装最新版 (1.12) Golang 并使用 go mod
- Python示例项目学习
- Linux下挂载超过2T的磁盘