龙空技术网

算法:和为s的连续正数序列

小猿陪学 96

前言:

而今各位老铁们对“连续点检测算法”可能比较注意,你们都想要了解一些“连续点检测算法”的相关文章。那么小编同时在网上收集了一些有关“连续点检测算法””的相关内容,希望咱们能喜欢,同学们快快来学习一下吧!

题目:

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例:

输入:target = 9输出:[[2,3,4],[4,5]]

思路:

滑动窗口

l和r指定了一个窗口,如果l和r只能向右侧移动,那么时间复杂度可以降低到O(n),这种移动的窗口称为滑动窗口。

此题中,如果窗口元素之和比目标值小,那么r右移扩大窗口;如果窗口元素之和比目标值大,那么l右移缩小窗口;如果窗口元素之和与目标值相同,那么保存当前窗口元素,然后l右移,继续检测下一个符合条件的窗口。

代码:

class Solution {public:    vector<vector<int>> findContinuousSequence(int target) {        vector<vector<int>> result;        vector<int> v;        int l=1, r=2;        int range_sum=3;        while(l < r)        {            if(target == range_sum)            {                v.clear();                for(int i=l;i<=r;i++)                    v.push_back(i);                result.push_back(v);                range_sum-=l;                l++;                            }else if(target < range_sum)            {                range_sum-=l;                l++;            }else            {                r++;                range_sum+=r;            }        }        return result;    }};

标签: #连续点检测算法