本文共 1360 字，大约阅读时间需要 4 分钟。

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

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

示例一

输入：target = 9

思路

• 用双端队列维护一个连续的窗口，窗口代表了连续的子序列。

代码

class Solution {
   public:    vector
   
    
     > findContinuousSequence(int target) {
           deque
     
       q;        int sum = 0;        vector
      
       
        > ans;        for(int i = 1;i < target;i++){
                   q.push_back(i);            sum += i;            while(sum > target && !q.empty()){
                   sum = sum - q.front();                q.pop_front();            }              if(sum == target){
                   vector
        
          tmp; for(int i = 0;i < q.size();i++) tmp.push_back(q[i]); ans.push_back(tmp); } } return ans; }};
        
       
      
     
    
   

思路二

因为队列的操作带来额外的开销。我们直接使用双指针来维护这个窗口的大小。

class Solution {
   public:    vector
   
    
     > findContinuousSequence(int target) {
           vector
     
      
       > ans;        int l = 1, r = 1,sum = 0;        while(r < target - 1){
               sum += r;            r++;              while(sum > target){
                   sum -= l;                l++;            }             if(sum == target){
                   vector
       
         tmp;                for(int i = l;i < r;i++) tmp.push_back(i);                ans.push_back(tmp);            }         }        return ans;    }};
       
      
     
    
   

转载地址：https://blog.csdn.net/free1993/article/details/115088845 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！