题目

和为s的连续正数序列

一、双指针实现滑动窗口

57.1.和为s的数字
和为s的正整数序列一定是在【1，2，……，s-1】这个数组中出现的。
仍旧设置两个指针：l,r 分别为1，2（因为这个子序列里至少有两个数字）。
l -> r 的子序列的和 < s 时，r可继续扩展，+1
l -> r 的子序列的和 > s 时，l+1
l -> r 的子序列的和 = s 时， 将这个子序列放入结果中，l+1继续寻找

l -> r 的子序列 是一个第一项为l，公差为1 的等差序列。求和时使用等差数列的求和公式：

def find_arr_with_sum_s_1(target):
    l, r = 1, 2
    res = []
    while l < r < target:
        sub_sum = int((r - l + 1) * (r + l) / 2)
        if sub_sum < target:
            r += 1
        elif sub_sum > target:
            l += 1
        else:
            res.append(list(range(l, r + 1)))
            l += 1
    return res

时间复杂度：由于两个指针移动均单调不减，且最多移动 target/2 次，即方法一提到的枚举的上界，所以时间复杂度为 O(target) 。

空间复杂度：O(1) ，除了答案数组只需要常数的空间存放若干变量。

最后

以上就是儒雅玫瑰为你收集整理的剑指offer实践 ——57.2.和为s的连续正数序列（python版)题目一、双指针实现滑动窗口的全部内容，希望文章能够帮你解决剑指offer实践 ——57.2.和为s的连续正数序列（python版)题目一、双指针实现滑动窗口所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。