题解 | #和为S的连续正数序列#

第七十三题 好题

双指针 指向左右边界

如果小于sum 右指针右移，如果大于sum左指针右移

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        // 例子：234 45
        // 先找到最开始的234 返回 然后删除2 往后判断 删除3 往后判断 得到5可以。
        vector<vector<int>> retans;
        int p=1,q=1;
        int temp=0;
        
        // 因为至少两个数，所以左边界肯定小于sum的一半
        while(p<=sum/2){
            // 如果加起来的和小于sum，则扩充右边界
            if(temp<sum){
                temp+=q;
                q++;
            }
            // 如果加起来的和大于sum，则删除最左边一个，即左指针p++
            else if(temp > sum)
            {
                temp-=p;
                p++;
            }
            // 如果结果是sum，则根据左右界限，吧pq存到一维数组中，再把数组存到返回答案中
            else if(temp==sum)
            {
                vector<int>tempans;
                for(int j=p;j<q;j++)
                    tempans.push_back(j);
                retans.push_back(tempans);
                // 此时找到了234 然后删除掉最左边的指针，在继续向后遍历
                // 变为34 < 9，则变为345
                // 345 > 9 删除3，得到45
                // 45符合要求，存入，变为5....再向后遍历直到循环结束
                temp-=p;
                p++;
            }
        }
        return retans;
    }
};