题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出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;
}

最新文章

  1. Flink &ndash; window operator
  2. 领导让我重新做一个微信H5页面!
  3. 【BZOJ 4326】【NOIP2015】运输计划
  4. Qt修改xml文件
  5. MS 数据库存储过程加密解密
  6. 第九篇、CSS布局
  7. Qt 学习之路 :文件
  8. MYSQL可调用执行自定义SQL的代码
  9. 适配iOS11
  10. .NET程序员所需要注意的网站资源
  11. spark的运行模式
  12. HTML语言发展史
  13. 【ARTS】01_15_左耳听风-20190218~20190224
  14. 怎么将APE转MP3,APE转MP3的方法
  15. css3 实现图片等比例放大与缩小
  16. 根据txt中的文件名将文件复制到目标文件夹中
  17. VMWARE虚拟机不显示主机共享的文件夹解决办法
  18. html中控制Tab键的顺序
  19. Sql server bulk insert
  20. Kconfig详解

热门文章

  1. 工作拾记 - 关于easyui模板后台改为vue-element
  2. PHP入门之调试
  3. 牛客网 牛客练习赛4 A.Laptop-二维偏序+离散化+树状数组
  4. docker时区问题
  5. 组合模式( Composite Pattern)
  6. opencv 图像resize
  7. Anaconda更新失败简单解决[CondaHTTPError: HTTP 000 CONNECTION FAILED for url]
  8. Ubuntu 安装最新版 (1.12) Golang 并使用 go mod
  9. Python示例项目学习
  10. Linux下挂载超过2T的磁盘