首页 > 试题广场 >

和为S的连续正数序列

[编程题]和为S的连续正数序列

热度指数：506605 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

数据范围： $0 < n \le 100$
进阶：时间复杂度 $O(n)$

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

示例1

输入

输出

[[2,3,4],[4,5]]

示例2

输入

输出

[]

算法知识视频讲解

查看答案及解析

推荐

Java

我去个地方啊

在答案区找到一个答案，说的很好，叫做双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度。非常牛逼的思路，虽然双指针或者所谓的滑动窗口技巧还是蛮常见的，但是这一题还真想不到这个思路。

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        //存放结果
        ArrayList<ArrayList<Integer> > result = new ArrayList<>();
        //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
        int plow = 1,phigh = 2;
        while(phigh > plow){
            //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            //相等，那么就将窗口范围的所有数添加进结果集
            if(cur == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int i=plow;i<=phigh;i++){
                    list.add(i);
                }
                result.add(list);
                plow++;
            //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
            }else if(cur < sum){
                phigh++;
            }else{
            //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                plow++;
            }
        }
        return result;
    }
}

编辑于 2019-02-13 19:50:27 回复(91)

Python

LYC_ley

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        i = 0
        if tsum <=2:
            return None
        res1 = []
        for i in range(1,tsum):
            n = 2
            sum = i
            
            while sum<tsum:
                sum = sum + i+n-1
                n = n+1
                if sum == tsum:
                    res1.append([x for x in range(i,i+n-1)])
                if sum >= tsum:
                    break
        return res1
滑动窗口

发表于 2021-08-22 14:48:07 回复(0)

Python

奋斗的习习张

# -*- coding:utf-8 -*-
# 思路比较简单，首先根据输入的数值和可以确定连续的数字的基本范围array
# 假设和为tsum的连续正整数为n个，则它们的平均值为tsum/n，那么这连续的几个正整数肯定在平均值左右，
# 这时只需要在平均值附件左右找n个数，如果和为tsum，则就是其中一个解...
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum <= 2:
            return []
        if tsum % 2:
            array = [i for i in range(1, tsum / 2 + 2)]
        else:
            array = [i for i in range(1, tsum / 2 + 1)]
        
        res = []
        for index in range(len(array), 1, -1):
            mean_value = tsum / index
            if tsum % index:
                temp = [mean_value, mean_value + 1]
            else:
                temp = [mean_value - 1, mean_value, mean_value + 1]
            while len(temp) != index:
                if temp[0] == 1 or temp[-1] == len(array):
                    break
                temp = [temp[0] - 1] + temp + [temp[-1] + 1]
            if sum(temp) == tsum:
                res.append(temp)
        return res

编辑于 2021-06-01 22:22:42 回复(0)

Python

二十一画生123

python：

1.运用数学知识得出连续序列的最大长度（math.sqrt(2*tsum)）

2.注意最后输出的顺序（所以第八行代码中为-1）

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        import math
        lis=[i for i in range(tsum)]
        ans=[]
        for n in range(int(math.sqrt(2*tsum)),1,-1):
            if n % 2 == 0 and (tsum % n)*2 == n:
                ans.append(lis[tsum/n-n/2+1:tsum/n+n/2+1])
            if n % 2 == 1 and tsum % n == 0:
                ans.append(lis[tsum/n-n/2:tsum/n+n/2+1])
        return ans

发表于 2021-05-23 23:01:32 回复(0)

Python

吾三省啊

# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
l = tsum/2+1
for i in range(1,l):
j = i+1
temp = i
while temp < tsum:
temp += j
j +=1
if temp == tsum:
res.append([x for x in range(i,j)])
return res

发表于 2021-05-05 13:50:49 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum<=0:
            return []
        i=1
        j=2
        res=[]
        while i<=tsum/2:
            l=[]
            for k in range(i,j+1):
                l.append(k)
            sum1=sum(l)
            if sum1==tsum:
                res.append(l)
                i=i+1
                j=i+1
            elif sum1<tsum:
                j+=1
            elif sum1>tsum:
                i+=1
        return res

发表于 2021-05-03 14:47:44 回复(0)

Python

Hiroi

Python 循环相加，等于就记录，大于就进行下一个起始位置的循环。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum<3:
            return []
        a = list(range(1,tsum))
        output = []
        for i in range(len(a)-1):
            for j in range(i+1,len(a)):
                temp = sum(a[i:j+1])
                if temp==tsum:
                    output.append(a[i:j+1])
                elif temp>tsum:
                    break
        return output

发表于 2021-04-18 20:04:04 回复(0)

Python

我一定要拿offer！！！

#根据等差数列的公式推导，n为长度，s为初始值

class Solution:

def FindContinuousSequence(self, tsum):
# write code here
res=[]
n=2
while (n*n+n)<=2*tsum:
if (2*tsum-n*n+n)%(2*n)==0:
s=(2*tsum-n*n+n)/(2*n)
ele=range(s,s+n)
res.append(ele)
n+=1
return res[::-1]

发表于 2021-04-17 10:22:29 回复(0)

Python

12313242

小白也能懂的思路：

输入一个所需要求的总和N。

1.从1开始做遍历，一直到N-1（因为至少两个数）。设该次遍历的数为a（a从1取值到N-1）

2.每次遍历里面，从a+1开始，计算从a到末尾值的和。设末尾值为b（b从a+1取值到N）。（和为(a+b)*(b-a+1)/2），一直到和等于或者大于N。如果等于N，则将a到b的列表记录下来。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        result = []
        for i in range(1,tsum):
            s = i + 1
            cum = 0
            while cum < tsum and s <= 100:
                cum = (i+s)*(s-i+1)/2
                if cum == tsum:
                    result.append(list(range(i,s+1)))
                s += 1
        return result

编辑于 2020-10-28 23:51:53 回复(0)

Python

老和山小学生

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        s = [1, 2]
        self.results = []
        while s[0] < tsum//2+1:
            if sum(s) < tsum:
                s.append(s[-1]+1)
            elif sum(s) > tsum:
                s.pop(0)
            else:
                self.results.append(s[:])    # deep copy
                s.pop(0)
        return self.results

发表于 2020-10-16 13:50:57 回复(0)

Python

qhzzZ0221

等差数列第n项：an=a1+(n-1)d

等差数列前n项和：s=a1*n+n*(n-1)/2

先拆分一下式子，可以看成两个部分，a1*n 和n(n-1)/2，对于左边，有两个变量a1和n，对于右边只有一个变量n。

我的想法是先让右边的部分，n*(n-1)/2的值满足小于s,在这个条件下，可以已知n，可以算出a1=(s-n(n-1)/2)/n。

只要保证a1算出来是整数，那么就可以找到这个序列range(a1,a1+n)。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        ans=[]
        if tsum<=2:
            return ans
        
        for i in range(2,tsum):
            q=i*(i-1)/2
            if q<tsum:
                if (tsum-q)%i==0:#保证a1是整数
                    a1=(tsum-q)/i
                    #i越大，list的开头的值就越小，
                    #所以每次用insert(0,obj),可以保证长的在前面
                    ans.insert(0,range(a1,a1+i))
            else:
                break
        
        return ans

发表于 2020-08-31 12:38:13 回复(0)

Python

将来的前端工程师

本题可以采用dfs深度遍历的方法实现，就是取连续值判断

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, n):
        # write code here
        def dfs(n,first,last,res):
            if sum(res) >= n:
                if sum(res) == n:
                    arr.append([i for i in res])
                return
            for i in range(first,last):
                res.append(i)
                dfs(n,i+1,i+2,res)
                res.pop()
        arr = []
        dfs(n,1,n,[])
        return arr

大家可以试一试通过深度遍历，一样可以ac

发表于 2020-08-27 00:35:41 回复(0)

Python

恶意上班

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        sm = 3
        left = 1
        right = 2
        result = []
        while left < right and right < tsum // 2 + 2:
            if sm == tsum:
                result.append([i for i in range(left, right + 1)])
                sm -= left
                left += 1
            elif sm < tsum:
                right += 1
                sm = sm+right
            else:
                sm -= left
                left += 1
        return result

双指针另一种写法

编辑于 2020-08-21 09:41:37 回复(0)

Python

Clairexx

求助大神们算法有什么问题？本地编辑器没有找到bug…

思路是找tsum应该分成奇数个还是偶数个，偶数个的话要求tsum/个数的小数点是0.5, 奇数个的话要求整除。

class Solution:
    def FindContinuousSequence(self,tsum):
        total=[]
        for i in range(tsum//2+1,1,-1):
            if i%2==0:
                if (tsum/i)%1==0.5 and int(tsum/i-0.5*(i-1))>0:
                    result=[int(tsum/i-0.5*(2*j+1)) for j in range(i//2)]+[int(tsum/i+0.5*(2*j+1)) for j in range(i//2)]
                    total.append(sorted(result))
            if i%2==1:
                if (tsum/i)%1==0 and int(tsum/i-i//2)>0:
                    result=[int(tsum//i)]+[int(tsum/i-j) for j in range(1,i//2+1)]+[int(tsum/i+j) for j in range(1,i//2+1)]
                    total.append(sorted(result))
        return(total)

发表于 2020-08-14 13:26:47 回复(0)

Python

Jerome0430

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        res = []
        #i为正数序列起始值，j为序列正数个数
        for i in range(1,tsum//2+1):
            for j in range(2,tsum):
                if (i+i+j-1)/2.0*j == tsum:
                    res.append([a for a in range(i,i+j)])
        return res

发表于 2020-08-10 11:20:49 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        #先考虑特殊情况
        if tsum < 3:
            return []
        array = []
        
        for i in range(1, tsum):
            t = 0
            j = i
            while t < tsum :
                t = t+j
                j += 1
            if t == tsum:
                array.append(range(i,j))
        return array

只想强调的是，return的用法：在上述写法总，由于return执行一次会跳出函数，所以，我们提前用array将各种结果序列存放起来，输出为：

如果我想单独列出来怎么办呢？

方1：

结:1：

方2：

结果2：

显然结果2不会比结果1多判断一个空序列，结果更干净。

发表于 2020-07-26 18:55:11 回复(0)

Python

风花月下

class Solution:
    def FindContinuousSequence(self, tsum):
        s=[]
        for i in range(1,tsum//2+1):
            b = pow( (2*tsum + pow(i-0.5, 2)), 0.5) - 0.5
            if b == int(b) and b > i:
                s.append(range(i,int(b+1)))
        return s

假设序列的最小值为a，最大值为b，b > a。那么序列求和为(a+b)(b-a+1)/2 = S,即(b+0.5)²-(a-0.5)²=2S,因此b = (2S+(a-0.5)²)^0.5-0.5，如果b是整数且大于a，那么b为一个解。

编辑于 2020-07-09 21:27:42 回复(0)

Python

青铜_ssk

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        ## 利用双指针的方法，a表示连续序列的开始，n表示连续序列的个数，total连续序列，利用的一个思想就是
        ## 当a越小n所需要的值越大。随着a不断增大n不断的减小。a的最小值为1，n的最大值为tsum-1
        a, n, total = 1, tsum-1, []
        index = 0
        while(a<tsum and n>0):
            ## 根据连续序列的开始和连续序列的个数求连续序列的和
            num = (2*a+n-1)*n/2
            if int(num)==tsum:
                index += 1
                total.append([i for i in range(a, a+n)])
            # 当和大于当前值，就是连续个数太多了，n进去1
            if num>tsum:
                n -= 1
            # 当和小于当前值，就是序列开始的值太小，需要往右走。
            else:
                a += 1
        if len(total)==0:
            return []
        else:
            return total

编辑于 2020-06-16 10:04:11 回复(0)

Python

窗外有千纸鹤

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        if tsum <= 2:
            return list()
        head = 1
        tail = 2
        res = list()
        while head < tail:
            tmp = tail * tail - head * head + head + tail
            if tmp == 2 * tsum:
                res.append(list(range(head, tail + 1)))
                head += 1
            elif tmp < 2 * tsum:
                tail += 1
            else:
                head += 1
        return res

一开始以为有什么简便方法，结果题目上方写到，本题知识点穷举，所以按照之前和为S的两个数那道题的解法来解就OK了，只是判断条件利用一下等差数列公式即可。

发表于 2020-06-08 20:49:21 回复(0)

Python

February2020

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        list1=[]
        for i in range(1, tsum):
            sum1 = i
            for j in range(i+1, tsum):
                sum1 += j
                if sum1 == tsum:
                    list1.append([m for m in range(i, j+1)])
                elif sum1 > tsum:
                    break
        return list1

发表于 2020-06-05 16:54:16 回复(0)

Python

Asdil

python版本双指针

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        l = list(range(1, tsum+1))
        i = 0
        j = 1
        ret = []
        while i<tsum:
            tmp = sum(l[i:j])
            if tmp == tsum: # 若等于
                if i+1==j: # 单个数字不算
                    pass
                else:
                    ret.append(l[i:j])
                i+=1
            elif tmp > tsum: #若大于前后缩减
                i+=1
                j-=1
            else:  #若小于继续加
                j += 1
        return ret

编辑于 2020-04-21 20:20:29 回复(0)