难度: Easy
待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。
注意，返回时需遵循以下规则：
示例 1：
输入：target = 12 输出：[[3, 4, 5]] 解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。
示例 2：
输入：target = 18 输出：[[3,4,5,6],[5,6,7]] 解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。
提示：
1 <= target <= 10^5运行时间: 172 ms
内存: 14.9 MB
from typing import List
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
left = 0
right = 0
window = 0
l = range(1, target//2+2)
res = list()
while right < len(l):
c = l[right]
right += 1
window += c
while window >= target:
if window == target:
res.append(list(l[left:right]))
d = l[left]
left += 1
window -= d
return res
if __name__ == '__main__':
s = Solution()
print(s.findContinuousSequence(15))
这道题目使用了滑动窗口的方法来解决。定义两个指针left和right，初始都指向序列的开始。然后逐步向右移动right指针，将对应的数加到当前窗口的和中（window）。如果窗口和大于目标值target，则逐步右移left指针，同时从window中减去相应的值，直到window小于等于target。如果在某一刻window等于target，当前的[left, right)范围内的数字就是一个有效的连续序列，我们将其记录下来。重复这个过程直到right到达序列的末尾。通过这种方式，可以找到所有符合条件的连续文件序列。
时间复杂度: O(n)
空间复杂度: O(n)
from typing import List
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
left = 0 # 初始化左指针
right = 0 # 初始化右指针
window = 0 # 当前窗口的数字和
l = range(1, target//2+2) # 可能的数字范围
res = list() # 存储结果的列表
while right < len(l): # 当右指针没有超出范围时
c = l[right] # 取得当前右指针指向的值
right += 1 # 右指针右移
window += c # 更新窗口和
while window >= target: # 当窗口和不小于目标时调整左指针
if window == target:
res.append(list(l[left:right])) # 如果窗口和等于目标，则记录结果
d = l[left] # 取得当前左指针指向的值
left += 1 # 左指针右移
window -= d # 更新窗口和
return res # 返回结果
if __name__ == '__main__':
s = Solution()
print(s.findContinuousSequence(15)) # 测试示例
在寻找连续整数序列的和等于target的情况下，考虑数字范围到 target/2 + 1 是因为任何超过 target/2 的数字无法与其它数字组成和为 target 的序列（最小的连续序列至少包含两个数字）。例如，如果 target 是 9，那么任何大于 4.5 的数字（即5及以上）将不能与其它数字组成和为 9 的序列。因此，将数字范围限制为 target/2 + 1 是为了确保所有可能的连续序列都被考虑到，同时避免不必要的计算。
当窗口和大于目标值时，意味着当前窗口包含的数字总和已经超出了目标值。此时，为了尝试减少总和以寻找可能的匹配，我们需要从窗口的左侧开始移除数字，即右移左指针。这样做是因为我们的目标是找到和为 target 的连续序列，而不是单个数字，因此需要通过调整窗口的大小（通过移动左指针）来找到可能的匹配序列。如果移动右指针，则会增加更多的数字到窗口中，使得窗口和更加超过目标值。
在滑动窗口算法中，每个数字最多被访问两次，一次是当它被添加到窗口中（即当右指针移到该数字上时），另一次是当它从窗口中移除（即当左指针移到该数字上时）。这种机制保证了每个数字只处理两次，从而使算法的时间复杂度为 O(n)，其中 n 是序列的长度。这种高效的遍历方式确保算法能够快速地找到所有符合条件的序列，而不会重复计算或进行不必要的计算。
如果 target 是一个较小的数，例如 2 或 3，该算法仍然可以正确运行。例如，对于 target=2，可能的连续序列只有一个：[1, 2]，其和为 2。对于 target=3，可能的连续序列也只有一个：[1, 2]，其和为 3。这些情况表明，算法也适用于较小的 target 值。