【剑指Offer】和为S的连续正数序列（双指针）

怼烎@ 2022-03-14 14:20 171阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_c451a3fd84b64cb19485dad758a55ebe_tpId_13_tqId_11194_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

##### 输出描述: #####

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

#### 解决方法 ####

双指针

class Solution { 
    public:
        vector<vector<int> > FindContinuousSequence(int sum) { 
            vector<vector<int> > res;
            if(sum<=0) return res;
            
            int left=1,right=1,sumN=1;
            while(left<=right && right<=sum){ 
                if(sumN<sum) { right++; sumN+=right;}
                else if(sumN>sum) { sumN-=left; left++;}
                else{ 
                    if(right-left>=1){ 
                        vector<int> temp;
                        for(int i=left;i<=right;i++) temp.push_back(i);
                        res.push_back(temp);
                    }                
                    sumN-=left; left++; 
                }
            }
            return res;
        }
    };

[https_www.nowcoder.com_practice_c451a3fd84b64cb19485dad758a55ebe_tpId_13_tqId_11194_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking