leetcode每日一题 python解法 3月6日
2020-03-06 本文已影响0人
Never肥宅
难度:简单
题目内容:
输入一个正整数 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
题解:
虽然来的早,但是内存消耗打败了100%的人我还是要骄傲一下吼
![](https://img.haomeiwen.com/i21470277/72419f74312c9447.png)
这个题我就不由得得吹嘘一下我自己了,第一次我做这个题的时候我就直接想出来了这种在线处理的算法,然后看教程从循环套循环到二分法我就觉得我好厉害啊直接就出来一个O(n)的方法
比较尴尬的就是二分法让我有点难。
好了来说这个算法吧,专业一点来讲就是双指针
第一个指针指向序列首端,另一个指向末端
如果序列满足自然就添加进list
如果不满足的话,如果大了,就让第一个指针+1,这样去掉一个数
如果小了就让第二个指针+1,这样就包括进来一个大一点的数
从左向右单向进行
虽然很简单但是我想出来的时候蛮激动的啊,就是特别想被夸的那种
代码
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
i = 1 #小的数字
j = 2 #大的数字
res =[]
while j<target:
if self.calSum(i,j) == target:
res.append(list(range(i,j+1)))
i += 1
elif self.calSum(i,j) < target:#那就需要增加数进来
j += 1
elif self.calSum(i,j) > target:#那就需要减少数进来
i += 1
return res
def calSum(self,x,y):
return (x+y)*(y-x+1)/2