和为s的连续正数序列 python_Python 面试题57 II. 和为s的连续正数序列

文章目录面试题57 – II. 和为s的连续正数序列题目解题思路代码实现实现效果

面试题57 – II. 和为s的连续正数序列

题目来源：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9

输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

解题思路

思路：等差数列求和

这里额外添加一个概念，末项与首项的间隔i。利用间隔 i，当求得首项时，可根据间隔求得末项。

尝试推导公式：

等差数列求和公式：

(x+y)∗(y−x+1)2frac{(x+y)*(y-x+1)}{2}2(x+y)∗(y−x+1)​

其中这里y 表示末项，x 表示首项。现在我们引入一个间隔的概念 i，那么可得 i=y−xi = y – xi=y−x，将其代入上面的公式中：

(2x+i)∗(i+1)2=targetfrac{(2x+i)*(i+1)}{2}=target2(2x+i)∗(i+1)​=target

上面的式子可简化成：

2xi+2x+i2+i=2∗target2xi+2x+i^2+i=2*target2xi+2x+i2+i=2∗target

最后可得：

x=target−i(i+1)2i+1x = frac{target-frac{i(i+1)}{2}}{i+1}x=i+1target−2i(i+1)​​

根据上面的公式就可以求得首项x，在这里 x 必须是正整数，则 x≥1x geq 1x≥1，且题目提出序列至少有两个数，那么 i≥1i geq 1i≥1，i+1≥2i+1 geq 2i+1≥2，将 x≥1,i+1≥2x geq 1,i + 1 geq 2x≥1,i+1≥2 两个限定条件代入式子中，可以得出限定条件 1：

target−i(i+1)2≥2target – frac{i(i+1)}{2} geq 2target−2i(i+1)​≥2

同时，因为 x 必须是正整数，所以上面的式子中：

target−i(i+1)2i+1 frac{target-frac{i(i+1)}{2}}{i+1}i+1target−2i(i+1)​​

这里所求得的结果，必须是整数，这就是限定条件 2。具体实现可用取模来判断。

那么根据这两个条件，用代码进行实现。

代码实现

class Solution:

def findContinuousSequence(self, target: int) -> List[List[int]]:

# i 代表间隔，res 表示返回序列

i, res = 1, []

# 这里就是限定条件 1

while target - i * (i + 1) * 0.5 >= 2: