首页 > 其他分享 >和为S的连续正数序列

和为S的连续正数序列

时间:2023-05-10 15:13:54浏览次数:23  
标签:int res sum ++ vector 连续 序列 正数 复杂度

暴力

枚举区间起点 i,对于每一个 i,找到最大的 j ,满足 ij 区间和<target

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int> > res;
        for (int i = 1; i < sum; i ++ )
        {
            int j=i,t=0;
            vector<int> q;
            while(t<sum)
            {
                t+=j;
                q.push_back(j);
                j++;
            }
            if(t==sum)  res.push_back(q);
        }
        return res;
    }
};

二分优化

寻找 j 的过程可以使用二分,复杂度降为O(nlogn)

双指针优化

可以发现,i 后移,j 单调后移,可以使用双指针优化掉一层循环,复杂度降为O(n)

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int> > res;
        for (int i = 1,j=1,s=0; i < sum; i ++ )
        {
            while(s<sum)
            {
                s+=j;
                j++;
            }
            if(s==sum)
            {
                vector<int> q;
                for (int k = i; k < j; k ++ )  q.push_back(k);
                res.push_back(q);
            }
            s-=i;
        }
        return res;
    }
};

标签:int,res,sum,++,vector,连续,序列,正数,复杂度
From: https://www.cnblogs.com/tangxibomb/p/17388012.html

相关文章

  • PSO优化LSTM做时间序列的预测,优化的是隐藏层单元数目,批处理大小,时间窗口大小,学习率等
    PSO优化LSTM做时间序列的预测,优化的是隐藏层单元数目,批处理大小,时间窗口大小,学习率等网络参数。ID:1888668442690309......
  • 列出真分数序列
    列出真分数序列:按递增顺序依次列出所有分母为40.分子小于40的最简分数。解题思路:利用for循环遍历所有分子的可能,在for循环中利用辗转相除法求出最大公约数,若最大公约数为1则输出,否则继续循环。代码:#include<iostream>#include<iomanip>usingnamespacestd;intmain(){......
  • requests标头在json序列化时报错TypeError: Object of type CaseInsensitiveDict is n
    requests的作者似乎为了解决header里大小写兼容的问题,而创建了大小写不敏感的数据结构CaseInsensitiveDict,具体分析可以参见:详解Requests中的数据结构CaseInsensitiveDict。requests返回的response_header即是一个CaseInsensitiveDict类型,而且我们知道response_header里通常并非......
  • 自定义 li 标签序列的样式
    第一步删除li标签的默认样式,取消::mark代理样式(默认样式)。第一步已经把默认样式取消了,自然没有了序号,使用CSS的counter()函数和counter-increment属性来自定义序列号。通过list-style-type:none删除li标签的默认样式在li标签样式中设置counter-increment:st......
  • mybatis 自定义序列号
    功能需求:每天的序列号从1开始,保留四位数,不足4位往前补01,新建一张表 CREATETABLE`sequence`(`day_id`dateDEFAULTNULLCOMMENT'账期',`name`varchar(50)COLLATEutf8mb4_binNOTNULLCOMMENT'序列的名字',`current_value`int(11)NOTNULLCOMMENT'序列......
  • 连续可导总结
    连续连续定义:\(\lim_{x->x_0^-}f(x)=f(x_0)\),为左连续\(\lim_{x->x_0^+}f(x)=f(x_0)\),为右连续以前认为,左右极限相等是错的,参考可去间断点,左右也相等,但是不连续这里纠正,函数极限存在相等不一定连续,应该是左连续等于右连续可导可导是左右导数存在且相等这里可导推......
  • R语言随机波动模型SV:马尔可夫蒙特卡罗法MCMC、正则化广义矩估计和准最大似然估计上证
    全文链接:http://tecdat.cn/?p=31162最近我们被客户要求撰写关于SV模型的研究报告,包括一些图形和统计输出本文做SV模型,选取马尔可夫蒙特卡罗法(MCMC)、正则化广义矩估计法和准最大似然估计法估计。模拟SV模型的估计方法:sim<-svsim(1000,mu=-9,phi=0.97,sigma=0.15)pr......
  • 【视频】时间序列分类方法:动态时间规整算法DTW和R语言实现|附代码数据
    原文链接:http://tecdat.cn/?p=22945最近我们被客户要求撰写关于动态时间规整算法的研究报告,包括一些图形和统计输出动态时间扭曲算法何时、如何以及为什么可以有力地取代常见的欧几里得距离,以更好地对时间序列数据进行分类时间序列分类的动态时间扭曲使用机器学习算法对时间序......
  • 时间序列的STL分解Python代码——以验潮站数据为例
    1.时间序列分解的作用和意义时间序列通常包括如下几种成分:一个时间序列包含三种影响因素: 长期趋势:在一个相当长的时间内表现为一种近似直线的持续向上、向下或平稳的趋势。季节变动:受季节变化影响所形成的一种长度和幅度固定的短期周期波动周期变动:与季节变动类似,但是波动......
  • 用Python语言进行时间序列ARIMA模型分析
    应用时间序列时间序列分析是一种重要的数据分析方法,应用广泛。以下列举了几个时间序列分析的应用场景:1.经济预测:时间序列分析可以用来分析经济数据,预测未来经济趋势和走向。例如,利用历史股市数据和经济指标进行时间序列分析,可以预测未来股市的走向。2.交通拥堵预测:时间......