Leetcode 和为s的连续正数序列

leetcoed

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]

思路

方法一：滑动窗口，快慢指针
用两个指针，分别寻找区间，使得区间的序列和为目标值
如果区间序列和大于目标值，则移动慢指针向前，快指针不用从慢指针的后一位开始重新遍历，而是仍然在原位置，因为移动慢指针后，区间序列和必定减小且小于等于目标和

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        if target <3:
            return []
        i = 0
        j = 1
        mid = target//2
        num = list(range(1,mid+2))
        res = []
        while i<= mid and j <=mid+1:
            tmp = sum(num[i:j])
            if tmp>target:
                i +=1
            if tmp < target:
                j+=1

            if tmp == target:
                res.append(num[i:j])
                i+=1
       return res

方法二：数学公式
设a,b分别为序列的起点值和终点值，连续个正整数之和=（a+b)(b-a+1)/2=target
设target = x*y
则a = (x+y-1)/2
b = (x-y+1)/2
并且b>a
求出所有符合条件的a,b

最后

以上就是自然黄豆为你收集整理的Leetcode 和为s的连续正数序列的全部内容，希望文章能够帮你解决Leetcode 和为s的连续正数序列所遇到的程序开发问题。

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