Sui Xin's Blog

[剑指Offer]和为S的连续正数序列

Posted on In Disqus:

题目描述

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

输出描述:

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

解题思路

  • 方法一：直接遍历数组；
  • 方法二：设置两个指针，初始分别指向1和2，如果两个指针之间的序列和小于S，则后一个指针后移一位，大于S时前一个指针后移一位，等于S时记录下来当前序列，然后指针后移一位。

代码

Python(2.7.3)

方法一：暴力解法

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
        res = []
        for i in range(1, tsum // 2 + 1):
            tmp = [i]
            tmp_sum = i
            for j in range(i + 1, tsum // 2 + 2):
                tmp.append(j)
                tmp_sum += j
                if tmp_sum == tsum:
                    res.append(tmp)
                    break
                elif tmp_sum > tsum:
                    break
        return res

运行时间：31ms
占用内存：5852k

方法二

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):
        # write code here
        res = []
        left, right = 1, 2
        mid = tsum // 2 + 1
        while left < mid:
            tmp_sum = (right - left + 1) * (left + right) / 2
            if tmp_sum > tsum:
                left += 1
            elif tmp_sum < tsum:
                right += 1
            else:
                cur = left
                tmp_ls = []
                while cur <= right:
                    tmp_ls.append(cur)
                    cur += 1
                res.append(tmp_ls)
                right += 1
        return res

运行时间：20ms
占用内存：5856k

Related Posts