剑指offer 和为S的连续正数序列

Posted on |

和为S的连续正数序列

题目

Leetcode 829.连续整数求和

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

方法

限制条件：至少包含两个连续的正整数

方法1：暴力求解（容易超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum<3: return []
        ans=[]
        # 确保从正数开始统计(1,N)
        for start in range(1,tsum+1):
            target=tsum
            i=start
            while target>0:
                target-=start
                start+=1
            # 确保必须包含两个数，即索引不能相等
            if target==0 and start-1!=i:
                ans.append([x for x in range(i,start)])
        return ans
  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$O(1)$

方法2

存在一整数n，使得$n+(n+1)+(n+2)+…+(n+d-1)=N$

$n \times d$能被d整除，那么整数n存在，那就有一个有效连续序列和等于N

A valid sum cannot have more than d ~= sqrt(N) elements, so this is in O(sqrt(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here

        # 排除边界条件，必须满足要求：至少两个连续的正整数
        if tsum<3:
            return []

        ans=[]
        for d in range(1,tsum+1):
            nd=tsum-d*(d-1)/2
            if nd<0:
                break
            # n不能为0，必须是正整数，至少为1；n也不能为tsum，至少需要两个正整数
            if nd%d==0 and nd/d!=0 and nd/d!=tsum:
                n=nd/d
                ans.append(range(n,n+d))
        ans.sort()
        return ans

方法3：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        if tsum < 3:
            return []
        small = 1
        big = 2
        middle = (tsum + 1)>>1
        curSum = small + big
        output = []
        while small < middle:
            if curSum == tsum:
                output.append(range(small, big+1))
                big += 1
                curSum += big
            elif curSum > tsum:
                curSum -= small
                small += 1
            else:
                big += 1
                curSum += big
        return output