《剑指offer》刷题系列——（五十一）和为s的两个数字

109 阅读 0 评论 72 点赞

我是靠谱客的博主天真啤酒，这篇文章主要介绍《剑指offer》刷题系列——（五十一）和为s的两个数字，现在分享给大家，希望可以做个参考。

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例：
输入：target = 9
输出：[[2,3,4],[4,5]]

思路

可以参考和为s的两个数字，用双指针解决。
用small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列之和小于s，则增加big，让序列包含更多的数字；如果从small到big的序列之和大于s，则从序列中去掉较小的值，即增加small的值。
因为序列中至少要有两个数字，所以small一直增加到(1+s)/2为止。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        if target==1 or target==2: return None
        res = []
        small = 1
        big = 2
        while small <= target//2:
            if self.mySum(small,big)==target:
                res.append([small+i for i in range(big-small+1)])
                big+=1
            elif self.mySum(small,big)<target:
                big+=1
            else:
                small+=1
        return res

    def mySum(self,a,b):
        return (a+b)*(b-a+1)/2