[Jianzhi offer] 57 - ii Continuous positive sequence with sum s

The finger of the sword Offer 57 - II. And for s Continuous positive sequence of

subject

  Enter a positive integer target , Output all and as target A sequence of continuous positive integers （ Contains at least two numbers ）. The numbers in the sequence are arranged from small to large , The different sequences are arranged in descending order according to the first number .

Ideas

• When the sum of windows is less than target When , The sum of windows needs to be increased , So expand the window , The right border of the window moves to the right
• When the sum of windows is greater than target When , The sum of windows needs to be reduced , So we need to narrow the window , The left edge of the window moves to the right
• When the sum of windows is exactly equal to target When , We need to record the results at this point . Let the window be [i, j)[i,j), So we've found one ii The sequence at the beginning , And the only one ii The sequence at the beginning , Next we need to find i+1i+1 The sequence at the beginning , So the left side of the window moves to the right

Code

class Solution {
    
public:
    vector<vector<int>> findContinuousSequence(int target) {
    
        int i = 1;//  Slide the left border of the window 
        int j = 1;  //  Slide the right border of the window 
        int sum = 0; //  The sum of the numbers in the sliding window 

        vector<vector<int>> res;//  Store the results of several sliding windows 


        while(i <= target / 2)
        {
    
            //  Expand the sliding window 
            if(sum < target)
            {
    
                //  The right border moves to the right 
                sum += j;
                j++;
            }
            else if(sum > target)
            {
    
                   //  Reduce the sliding window 
                sum -= i;
                i++;
            }
            else{
    
                //  Records of the results 
                vector<int> arr;

                //  Write all the numbers in the sliding window into the array arr in   Left closed right open interval 
                for(int k = i; k < j; k++)
                {
    
                    arr.push_back(k);
                }
                res.push_back(arr);

                //  After writing   Continue to find the next set of results   Slide the window to the right   subtract i that will do 
                sum -= i;
                i++;

            }
        }

        return res;
    }
};