和为S的连续正数序列

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

既然是数学问题，那么就用数学的方法来解决（笑）

无非就是一个等差数列求和的问题

等差数列求和公式：
$\frac{(x_{0}+x_{n})*n}{2}$

其中： $图片说明$

代入可得： $图片说明$ 并且 $图片说明$

满足正数的条件，所以 $图片说明$

可得： $图片说明$

算法复杂度： $图片说明$

接下来就可以愉快地写代码啦:

function FindContinuousSequence(sum)
{
    const res = [];
    if(sum <= 0) return res;
    let n=2, x0, each;
    while(n**2 + n <= 2*sum){
        x0 = (2*sum + n -  n**2) / (2*n);
        if(Math.floor(x0) === x0){
            each = [];
            for(let i=0; i<n; ++i) each.push(x0+i);
            res.push(each);
        }
        ++n;
    }
    return res.sort((a, b) => a[0]-b[0]);
}

全部评论

推荐最新楼层

曾经不是人

郑州大学电子信息类

事实上时间复杂度还是o(s),while循环有根号s层，而每找到一个n，都要循环生成一个长度为n的数组，所以时间复杂度为o(n^2)也就是o(s),另外最后不要用排序，每次插入的时候插入首部就可以了。

送花回复

发布于 2020-07-06 21:06

🎈选修2

Java

思路很棒，我用python重写的，只通过百分之33 啊 res=[] if tsum <0: return res n=2 while (n*n+1<=2*tsum): x0 = (2 *tsum + n - n ** 2) / (2 * n) if math.floor(x0)==x0: x0=math.floor(x0) #那么这个就是要的答案 templist=[] for i in range(n): templist.append(x0+i) res.append(templist) n+=1 res2 = [] for item in range(len(res)): res2.append(res.pop()) return res2

送花回复

发布于 2020-04-07 21:42

秋招专场

校招火热招聘中

官网直投

白色高跟鞋

Java

python https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe?f=discussion&toCommentId=5912793

送花回复

发布于 2020-04-17 18:06

灵修字忘归

测试工程师

我用C++ 为啥不对呢请指教 vector<vector><int> > FindContinuousSequence(int sum) { vector<vector><int> >dp; vector<int> res; if(sum<3) return dp; int n=2; int x1=1; while(pow(n,2)+n<=2*sum) { x1=(2*sum-pow(n,2)+n)/(n*2); if(((int)(2*sum-pow(n,2)+n))%((int)(n*2))!=0) return dp; for(int i=0;i</int></int></vector></int></vector>

送花回复

发布于 2020-05-29 22:14

榴花般的双眸

Java

求问为什么通过率只有33%呢 import java.util.*; public class Solution { public ArrayList<arraylist><integer> > FindContinuousSequence(int sum) { ArrayList<arraylist><integer>> result = new ArrayList<arraylist><integer>>(); int n=2,x0=2; while(2*sum >= n*n+n){ x0 = (2*sum-n*n+n)/(2*n); if(Math.floor(x0) == x0){ ArrayList<integer> Array = new ArrayList<integer>(); for(int i=0;i</integer></integer></integer></arraylist></integer></arraylist></integer></arraylist>

送花回复

发布于 2020-11-02 01:10