和为S的连续正数序列★★
2024-09-15 06:07:40
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
解题思路:
思路一:
自己想了一个复杂度为sum*log(sum)的想法,通过了所有case,但是感觉如果sum很大的话,可能会超时。其实就是对二分算法的改造,搜索左右区间的条件变成了判断
mid*(mid+1)/2-i*(i+1)/2 < sum ,也就是判断i到mid的和与sum的关系。
思路二:
看谈论区有滑动窗口的思路,之后研究
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > res;
if(sum < 2) return res;
for(int i= 0; i < sum; i++){
int l = i;
int r = sum-1;
int mid = (l+r)/2;
while(l <= r){
mid = (l+r)/2;
//cout<<"i="<<i <<" l="<<l<<" r="<<r <<" mid="<<mid <<" Cn="<<mid*(mid+1)/2 - i*(i+1)/2 <<endl;
if(mid*(mid+1)/2 - i*(i+1)/2 < sum){
l = mid+1;
}else if(mid*(mid+1)/2 - i*(i+1)/2 > sum){
r = mid-1;
}else{
break;
}
}
vector<int> vct;
if(mid*(mid+1)/2 - i*(i+1)/2 == sum){
//cout<<"i"<<i<<" mid"<<mid<<endl;
for(int j = i+1; j <= mid; j++){
if(j <= 0) continue;
vct.push_back(j);
}
if(vct.size() >= 2) res.push_back(vct);
}
}
return res;
}
};
最新文章
- JavaScript异步编程(2)- 先驱者:jsDeferred
- 记一道有意思的算法题Rotate Image(旋转图像)
- Tickets——H
- java 编码
- Passwordless SSH Login
- 如何查看LINUX 硬件配置信息
- shell中大小写转换
- poj2503 哈希
- ARM内核全解析,从ARM7,ARM9到Cortex-A7,A8,A9,A12,A15到Cortex-A53,A57
- Leetcode那点事儿
- &#183; HTML使用Viewport
- 《第一行代码》学习笔记30-内容提供器Content Provider(3)
- 关于jq操作table下多个type=radio的input的选中
- WinCE隐藏显示任务栏,当任务栏隐藏时将其显示,当任务栏显示时将其隐藏(FindWindow,ShowWindow,IsWindowVisible),
- 使用jQuery增加或删除元素(内容)
- 小玩意--自定义log记录
- web全栈架构师[笔记] — 02 数据交互
- [CodeChef]GERALD07/[JZOJ4739]Ztxz16学图论
- python 小白学习(1)
- 【附源文件】日记类App原型制作分享-Grid Diary
热门文章
- Jenkins权限管控
- PARTITION BY函数
- JSON is undefined. Infopath Form People Picker in SharePoint 2013
- Sublime写作
- 点击input消除默认背景颜色:focus
- KVM到KVM之v2v迁移
- “全栈2019”Java多线程第九章:判断线程是否存活isAlive()详解
- 域名可以解析(ping域名可以获取正确ip),服务器本地telnet 域名+端口 无法连接,通过建立本地虚拟域名指定的方法解决该问题
- 从【BZOJ4173】谈做题技巧
- Vulnhub Breach1.0