前言:
而今各位老铁们对“连续点检测算法”可能比较注意,你们都想要了解一些“连续点检测算法”的相关文章。那么小编同时在网上收集了一些有关“连续点检测算法””的相关内容,希望咱们能喜欢,同学们快快来学习一下吧!题目:
输入一个正整数 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; }};
标签: #连续点检测算法