跟着姚桑学算法-和为S的连续正数序列

简介: 剑指offer算法

题. 和为S的连续正数序列

输入一个非负整数 S,打印出所有和为 S 的连续正数序列(至少含有两个数)。

例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。

数据范围

0≤S≤1000

样例

输入:15

输出:[[1,2,3,4,5],[4,5,6],[7,8]]

【题解】--- 双指针

双指针算法最核心的用途就是优化时间复杂度。

【核心思想】:

原本两个指针是有 种组合,因此时间复杂度是 。
而双指针算法就是运用单调性使得指针只能单向移动,因此总的时间复杂度只有 ,也就是。
之所以双指针可以实现 的时间复杂度是因为指针只能单向移动,没有指针的回溯,而且每一步都会有指针移动。

而朴素的 算法的问题就在于指针经常回溯到之前的位置。

本题设置两个指针 ij,分别指向连续正数序列的起始和终止;

用s表示当前连续正数序列的和,即s=i+(i+1)+…+j;

以i递增的方式遍历整个序列(1到n),代表查找以i开头的时候结尾j应该是多少。当s<sums说明j应该往后移动,当s=sums说明满足题意,当s>sums说明向后走即可。

注意上述遍历过程中,s=sums的情况下不需要把j往前移动,原因是当进入下一个循环前s−=i,即(i+1)到j的和肯定小于sum。

复杂度分析:

时间复杂度是O(n^2)。

C++代码实现:

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;
        for (int i = 1, j = 1, s = 1; i <= sum; i ++ )
        {
            while (s < sum) j ++, s += j;
            if (s == sum && j > i)
            {
                vector<int> line;
                for (int k = i; k <= j; k ++ ) line.push_back(k);
                res.push_back(line);
            }
            s -= i;
        }
        return res;
    }
};
目录
相关文章
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
76 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
3月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
160 19
|
3月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
|
4月前
|
机器学习/深度学习 数据采集 算法
【优秀python算法毕设】基于python时间序列模型分析气温变化趋势的设计与实现
本文介绍了一个基于Python的时间序列模型,用于分析和预测2021-2022年重庆地区的气温变化趋势,通过ARIMA和LSTM模型的应用,揭示了气温的季节性和趋势性变化,并提供了对未来气温变化的预测,有助于气象预报和相关决策制定。
111 1
【优秀python算法毕设】基于python时间序列模型分析气温变化趋势的设计与实现
|
5月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
296 1
|
4月前
|
算法
【算法】栈算法——栈的压入、弹出序列
【算法】栈算法——栈的压入、弹出序列
|
4月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
43 0
|
5月前
|
机器学习/深度学习 数据采集 算法
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
379 2
|
6月前
|
机器学习/深度学习 人工智能 算法
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
146 0
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
|
6月前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
66 0