LeetCode面试题57-Ⅱ。连续正数序列和为s[简易][Python][滑动窗口][数学]问题是输入一个正整数target，输出所有以和为target的连续正整数序列（至少包含两个数）。序列中的数字从小到大排列，不同的序列按照第一个数字从小到大排列。示例1：输入：target=9输出：[[2,3,4],[4,5]]示例2：输入：target=15输出：[[1,2,3,4,5],[4,5,6],[7,8]]限制：1<=target<=10^5思路解1.滑动窗口的i指针表示窗口左边界，j指针表示右边界的窗口。当sumtarget时，第i个指针向右移动。当sum=target时，将window中的数组加到res中，将i指针右移。请注意，窗口的范围是左闭右开[)。时间复杂度：O(n)Python3代码类解决方法：deffindContinuousSequence(self,target:int)->List[List[int]]:#解决方法一：滑动窗口i,j=1,1sum=0res=[]whilei<=target//2:ifsumtarget:#i+1sum-=ii+=1else:arr=list(range(i,j))res.append(arr)#i+1sum-=ii+=1returnres第二个求根公式可以看成是等差数列，于是想到求和公式：$$S_n=\frac{n}{2}(a+a_n)$$设x为第一项，y为最后一项，则y-x+1为项数。令和为目标：$$target=\frac{(x+y)*(y-x+1)}{2}$$展开上面的公式：$$x^2-x-y^2-y+2*target=0$$根据求根公式：$$x_{1,2}=\frac{-b\pm\\sqrt{b^2-4ac}}{2a}$$去掉负根，可以得到如下公式：$$x=\sqrt{y^2+y-2*target+\frac{1}{4}}-\frac{1}{2}$$Python3codeclass解法：deffindContinuousSequence(self,target:int)->List[List[int]]:#解决方案二：公式res=[]foryinrange(1,target//2+2):#range:[)x=(1/4+y**2+y-2*target)**(1/2)+0.5iftype(x)!=complexandx-int(x)==0:#x不能是复数并且xmustbeintres.append(list(range(int(x),y+1)))returnres解三区间法根据解二的求根公式，代入i=y-x得到：$$target=\frac{(2x+i)*(i+1)}{2}$$进一步简化得到：$$target=x(i+1)+\frac{i(i+1)}{2}$$最后得到：$$x=\frac{target-\frac{i(i+1)}{2}}{i+1}$$这样，得到两个条件：1.i(i+1)/2必须是l低于target2。分子必须能被分母整除Python3codeclassSolution:deffindContinuousSequence(self,target:int)->List[List[int]]:#solutionthreei,res=1,[]whilei*(i+1)/2求根法->区间法，一座山还有另一座山高
