剑指Offer——和为S的连续正数序列

时间:2023-02-18 15:01:28

题目描述:

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 
输入描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

分析:

假设 i,j 分别是第一个数和最后一个数,那么根据 (i+j)*(j-i+1)/2=sum 可得 i+j-i^2+j^2=2*sum 。遍历i从1到sum/2,求j。
由于 j+j^2=2*sum-i^2-i ,所以 j 可能取 floor(sqrt(2*sum-i^2-i)) ,如果 j 可取,则将 i 到 j 加入数组中。

代码:

 class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > seqs;
for(int i = ; i <= (sum >> ); i++) {
int j = floor(sqrt((sum << ) + i * i - i));
if(i < j && i + j - i * i + j * j == (sum << )) {
vector<int> seq;
for(int k = i; k <= j; k++)
seq.push_back(k);
seqs.push_back(seq);
}
}
return seqs;
}
};

剑指Offer——和为S的连续正数序列的更多相关文章

  1. 【Java】 剑指offer&lpar;57-2&rpar; 为s的连续正数序列

      本文参考自<剑指offer>一书,代码采用Java语言. 更多:<剑指Offer>Java实现合集   题目 输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数 ...

  2. 剑指Offer之和为S的连续正数序列

    题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100.但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数).没多久,他 ...

  3. 剑指 Offer——和为 S 的连续正数序列

    1. 题目 2. 解答 定义两个指针,刚开始分别指向 1 和 2,求出位于这两个指针之间的元素和.如果和大于 S,前面的指针向后移直到和不大于 S 为止:反之,如果和等于 S,则此时两个指针之间的元素 ...

  4. 剑指Offer40 和为s的连续正数序列

    /************************************************************************* > File Name: 40_Contin ...

  5. 剑指Offer-41&period;和为S的连续正数序列&lpar;C&plus;&plus;&sol;Java&rpar;

    题目: 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100.但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数).没多久,他就 ...

  6. 剑指:和为S的连续正数序列

    题目描述 输入一个正数 s,打印出所有和为 s 的连续正数序列(至少含有两个数). 例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1-5.4-6 ...

  7. 6-剑指offer&colon; 和为S的连续正数序列

    题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100.但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数).没多久,他 ...

  8. 《剑指offer》栈的插入弹出序列

    本题来自<剑指offer> 栈的插入弹出序列 题目: 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2, ...

  9. C&plus;&plus;版 - 剑指offer 面试题31:连续子数组的最大和 题解

    剑指offer:连续子数组的最大和 提交网址: http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&am ...

随机推荐

  1. USB2&period;0协议笔记

    1.概述     USB(Universal Serial Bus)具有传输速率快,可热插拔等显著特点,应用已经十分广泛,目前的相当多的设备已经支持最新的USB3.0协议.理论上USB1.1的传输速度 ...

  2. &lbrack;Android Tips&rsqb; 3&period; Launch CallLog Activity

    Intent intent = new Intent(Intent.ACTION_VIEW); intent.setData(android.provider.CallLog.Calls.CONTEN ...

  3. 关于&period;NET邮件的收发问题总结

    转载:http://www.cnblogs.com/ustb*/archive/2007/05/28/762581.html //取数据库中邮件信息中的最大发送时间,即最近接收到的一封邮件的时间 ...

  4. MySQL的InnoDB和MyISAM比较

    InnoDB 1)虽然不支持用户创建聚族索引,但InnoDB会对主键建立聚簇索引.如果你不指定主键,InnoDB会用一个具有唯一且非空值的索引来代替.如果不存在这样的索引,InnoDB会定义一个隐藏的 ...

  5. nginx自动切割访问日志

    Web 访问日志 (access_log) 记录了所有外部客户端对Web服务器的访问行为,包含了客户端IP,访问日期,访问的URL资源,服务器返回的HTTP状态码等重要信息. 一条典型的Web访问日志 ...

  6. float的精度&comma;3个小数相加后精度丢失--小数比较使用bccomp&lpar;&rpar;方法

    $a = 1200.00;$b = 1199.80;$c = 0.1;$u = 0.12; $d = $b+$c+$u;var_dump($a);var_dump($d);var_dump(bccom ...

  7. 我的android学习脚步----------- 的第一个应用

    刚刚开始学android开发,以前都是在别人调好的应用中修改JNI,现在需要自己一步步走 开发环境:Eclipse+ADT 配置不多讲了,引自:http://www.cnblogs.com/allen ...

  8. Elasticsearch高级搜索排序( 中文&plus;拼音&plus;首字母&plus;简繁转换&plus;特殊符号过滤)

    一.先摆需求: 1.中文搜索.英文搜索.中英混搜   如:"南京东路","cafe 南京东路店" 2.全拼搜索.首字母搜索.中文+全拼.中文+首字母混搜   如 ...

  9. php项目核心业务(增、删、改、查)(第三篇)

    对增删改查数据库的封装 //php对数据库的封装 //Mysql_fetach($sql)函数查询所有的 function Mysql_fetach($sql){ $conn=mysqli_conne ...

  10. POJ 3253 Fence Repair STL 优先队列

    这题做完后觉得很水,主要的想法就是逆过程思考,原题是截断,可以想成是拼装,一共有n根木棍,最后要拼成一根完整的,每两根小的拼成一根大的,拼成后的木棍长度就是费用,要求费用最少.显然的是一共会拼接n-1 ...