leetcode 面试题57 - II. 和为s的连续正数序列

电玩女神 2023-07-11 15:01 21阅读 0赞

队列的简单应用。

思路就是先一直往后面加，直到值》=target ，然后在考虑从前面减。

class Solution {
    public:
        vector<vector<int>> findContinuousSequence(int target) {
            vector<vector<int> > ans;
            queue<int> que;
            int k=1;
            int sum=0;
            while(k<target)
            {
                sum+=k;
                que.push(k);
                if(sum>target)
                {
                    while(sum>target)
                    {
                        sum-=que.front();
                        que.pop();
                    }
                }
                if(sum==target)
                {
                    vector<int> tmp;
                    for(int i=que.front();i<que.front()+que.size();i++)
                    {
                        tmp.push_back(i);
                    }
                    sum-=que.front();
                    que.pop();
                    ans.push_back(tmp);
                }
                k++;
            }
            return ans;
        }
    };