「LeetCode每日一题」——LCOF.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]]
限制:
1 <= target <= 10^5
思路
根据题意,我们开始想到的解法应该是双指针遍历。可以使用双指针范围内数组之和与target进行判断,符合条件的数组添加进入结果列表中,然后动态地维护两个指针缓缓前进,直到右边界到达target的中值即可。
现在我们先来了解一下什么叫滑动窗口
滑动窗口
可以先来先理解一下窗口的概念
假设target是9,我们的脑海中可以快速的浮现出一个从1到9的数组。这时候不妨再想象一下,数组下方有个两个指针,一个指向1,一个指向5,两个指针形成的这个数组范围,就是所谓的窗口。如下图所示:


请问滑动作何解释?
左右指针通过平移,会改变了窗口的范围,从而引起窗口的滑动,这就是所谓的滑动窗口




针对目前这个题,我们可以把左指针i指向1,右指针j指向2,然后就能计算出当前窗口范围各数字的和,cur_sum = sum(list(range(i,j+1))),如果cur_sum小于target,说明当前窗口数字之和过小,这时候咱们可以令j += 1,这样我们的新窗口就向右边扩大了。同样的道理,如果cur_sum大于target,这说明我们当前窗口数字之和过大,这时候就令i += 1,这样窗口的左边界就向右边移动了一个单位,就使得窗口变小了。
观察上图,前面窗口的指针是i=1,j=5,形成的窗口就是[1,2,3,4,5],那么cur_sum就是1+2+3+4+5=15
由于左指针i向右平移,后面窗口的指针是i=4,j=5,形成的窗口就是[4,5],那么cur_sum就是4+5=9
代码如下:
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
# 初始化窗口指针和输出列表
i, j, res = 1,2, []
# 滑动窗口的右边界不能超过target的中值
while j <= target//2 + 1:
# 计算当前窗口内数字之和
cur_sum = sum(list(range(i,j+1)))
# 若和小于目标,右指针向右移动,扩大窗口
if cur_sum < target:
j += 1
# 若和大于目标,左指针向右移动,减小窗口
elif cur_sum > target:
i += 1
# 相等就把指针形成的窗口添加进输出列表中
# 别忘了,这里还要继续扩大寻找下一个可能的窗口哦
else:
res.append(list(range(i,j+1)))
# 这里用j+=1,i+=1,i+=2都可以的
j += 1
return res
这题其实还能把公式写出来,留给大家探索吧。
方案代码
双指针解法:
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
i, j, res = 1,2, []
while j <= target//2 + 1:
cur_sum = sum(list(range(i,j+1)))
if cur_sum < target:
j += 1
elif cur_sum > target:
i += 1
else:
res.append(list(range(i,j+1)))
j += 1
return res
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/206.html
您必须登录才能发表评论。