题解 | 数学思路,复杂度为根号n。#和为S的连续正数序列#

和为S的连续正数序列

http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe


偏数学思路

看大家都在双指针滑动窗口,要么就是遍历。
提供一个偏数学的思路。十行代码解决问题,复杂度为
等差数列的数字个数为n,起始数字为a,
主要思路是在合适范围内遍历n,然后求解a判断是否为整数,若为整数则ok。
代码如下,具体公式推导在后边。
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        double n =int(0.5+sqrt(2*sum+1/4));//数列长度上限
        vector<vector<int>> res;
        while(n>1){
            if(sum/n+(1-n)/2 - int(sum/n+(1-n)/2)==0){//判断计算结果为整数,sum/n+(1-n)/2表示的是数列第一个数字。
            vector<int> res_unit(n);//其中一种结果
            iota(res_unit.begin(),res_unit.end(),sum/n+(1-n)/2);//生成一个起始为sum/n+(1-n)/2,长度为n的数列。
            res.push_back(res_unit);}//所有的结果
            n--;}
        return res;}};


公式推导

设等差数列的数字个数为n,起始数字为a,其和为sum,则满足
可以得到

其中在本题定义域内,n是a的减函数,取a = 1,可得

可以将n的范围确定下来,大概在2和之间,复杂度为级别。
接下来遍历n,求解a


若a为整数,则是一种合格的情况。

全部评论
来个人顶一顶
2 回复 分享
发布于 2021-04-17 23:01
double n =int(-0.5+sqrt(2*sum+0.25));//数列长度上限
点赞 回复 分享
发布于 2021-10-14 23:13
你的第一个公式打错了
点赞 回复 分享
发布于 2021-07-08 22:14

相关推荐

野猪不是猪🐗:我assume that你must技术aspect是solid的,temperament也挺good的,however面试不太serious,generally会feel style上不够sharp
点赞 评论 收藏
分享
评论
7
3
分享

创作者周榜

更多
牛客网
牛客企业服务