题解 | #和为S的连续正数序列#

题目：https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe

法一：求根公式。 题解区Maokt思路，搬运流程图。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param sum int整型 
# @return int整型二维数组
#
class Solution:
    def FindContinuousSequence(self , sum: int) -> List[List[int]]:
        res=[]
        for left in range(1,sum):
            right=((-1)+(1+4*(left**2-left+2*sum))**0.5)/2
            if right>left and right%1==0:
                mylist=list(range(left,int(right)+1))
                res.append(mylist)
        return res

代码里的循环条件用 while left < right其实更好，减少循环次数。

法二：双指针。 类似#和为S的两个数字# https://blog.nowcoder.net/n/65e73e6ce7dc42368ed68f070a24f1e9 思路。

step 1：准备左右双指针从区间[1,2]开始搜索。

step 2：如果两个指针的区间和等于目标和，则找到了一个解，此时左指针可以右移开始找一个解。

step 3：如果两个指针的区间和小于目标和，说明区间要扩大，因此右指针右移；如果两个指针的区间和大于目标和，说明区间要缩小，因此左指针右移。

step 4：当两指针对撞停止寻找。

区间和等于(l+r)∗(r−l+1)/2。

class Solution:
    def FindContinuousSequence(self , sum: int) -> List[List[int]]:
        res=[]
        left=1
        right=2
        while left<right:
            if (left+right)*(right-left+1)/2<sum:
                right=right+1                
            elif (left+right)*(right-left+1)/2>sum:
                left=left+1
            else:
                mylist=list(range(left,right+1))
                res.append(mylist)
                left=left+1
        return res