美文网首页
slide window

slide window

作者: 极速魔法 | 来源:发表于2017-07-18 14:16 被阅读69次

given a sum,find continous nums add equals sum
like 100= 9 10 11 12 13 14 15 16;
=18 19 20 21 22

#include <iostream>
#include <vector>


using namespace std;

class Solution{
public:
    vector<vector<int> > findSequence(int sum){
        //slide window,watch out start ,end 
        int start=0,end=0,size=sum-1;
        
        vector<vector<int> >res;
        vector<int> vec;
        if(sum<=2){
            return res;
        }
        //init
        vector<int> arr(size);
        for(int i=1;i<sum;i++){
            arr[i-1]=i;
        }
        int subSum=arr[0];

        while(start<=size-2 && end<=size-1){
            //[start...end]
            while(subSum<sum){
                end++;
                subSum+=arr[end];
                
                
            }
            
            while(subSum>sum){
                //[start...end]
                subSum-=arr[start];
                start++;
            }

            if(subSum==sum){
                for(int i=start;i<=end;i++){
                    vec.push_back(arr[i]);
                }
                res.push_back(vec);
                vec.clear();
                end++;
                subSum+=arr[end];
            }
        }

        return res;

    }
};

int main(){
    int sum=100;
    vector<vector<int> > res;
    res=Solution().findSequence(sum);
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size();j++){
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }
}

相关文章

网友评论

      本文标题:slide window

      本文链接:https://www.haomeiwen.com/subject/ewqhkxtx.html