当前位置 博文首页 > 中流击水,浪遏飞舟:滑动窗口优化&&剑指 Offer 57 - II

    中流击水,浪遏飞舟:滑动窗口优化&&剑指 Offer 57 - II

    作者:[db:作者] 时间:2021-08-26 12:44

    1.原始写的冗长滑动窗口代码(用了queue数据结构

    class Solution {
    public:
        vector<vector<int>> findContinuousSequence(int target) {
            vector<vector<int>>ans;
            queue<int>q;    //队列遍历到数组中点
            int mid=(target+1)/2;
            int sum=0;
            int R=1;
            while(R<=mid+1){
                if(sum==target){
                    queue<int>p;
                    p=q;
                    vector<int>tmp;
                    while(!p.empty()){
                        tmp.push_back(p.front());
                        p.pop();
                    }
                    ans.push_back(tmp);
                    q.push(R);
                    sum+=(R++);
                }
                else if(sum<target){
                    q.push(R);
                    sum+=(R++);
                }
                else{
                    sum-=q.front();
                    q.pop();
                }
            }
            return ans;
        }
    };
    

    2.优化(queue可以用双指针代替

    参考力扣大佬题解:
    剑指 Offer 57 - II. 和为 s 的连续正数序列(求和公式 / 滑动窗口,清晰图解)

    class Solution {
    public:
        vector<vector<int>> findContinuousSequence(int target) {
            vector<vector<int>>ans;
            int i=1,j=2,s=3;
            int mid=(target+1)/2;
            while(j<=mid+1){
                if(s==target){
                    int k=i;
                    vector<int>tmp;
                    while(k<=j){
                        tmp.push_back(k++);
                    }
                    ans.push_back(tmp);
                    s+=(++j);
                }
                else if(s<target){
                    s+=(++j);
                }
                else{
                    s-=(i++);
                }
            }
            return ans;
        }
    };
    
    cs
    下一篇:没有了