41.和为S的连续正数序列.md

41.和为S的连续正数序列

题目描述

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

输出描述

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

 

解题思路

下面的思路来自《剑指offer》。

• 首先思考一个简单一点的问题：

  在递增的排序数组中找到两个数，使它们的和正好是S，如果有多对数字满足要求的话，任意输出一对就行。

  最容易想到的复杂度为$O(n^2)$的算法为，首先固定一个数，然后把剩下的所有数字和它相加。但这种方法效率太低了，因此想到另外一种方法，由于数组是排序的，因此可以设置两个指针，分别指向数组的头(small)和尾(big)，当两个指针指向数字之和小于S的时候，将small指针向后移动，如果两个数字之和大于S的话就把big指针向前移动，最终一定能找到这对数字，复杂度为$O(n)$。

• 再用类似的思路来思考本题，可以设置两个指针small和big，分别初始化为1和2，当两个指针之间的连续数组的和小于S时，将big指针向后移动，增加一个大的数字；当连续数组之和大于S时，将small向后移动，减少一个小的数字；当连续数组的和等于S时，将结果保存，并增大big，不选择增大small的原因是如果small和big已经挨着了，再增大small的话它们就相等了（比如S=101, small=50, big=51的时候）。直到small指针移动到(S+1)/2的位置为止，因为题目要求至少包括两个数。

  在求连续数组的和的时候可以在上次的和的基础上加或者减，提高求和效率。

 

代码

• C++

class Solution {
private:
    void insertSequence(vector<vector<int>> &result, int small, int big){
        vector<int> temp;
        for(int i=small;i<=big;i++){
            temp.push_back(i);
        }
        result.push_back(temp);
    }
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> result;
        if(sum<3) return result;
        
        int small=1, big=2, curSum=3;
        int middle = (sum+1)/2;
        while(small < middle){
            if(curSum < sum){
                big++;
                curSum += big;
            }else if(curSum > sum){
                curSum -= small;
                small++;
            }else{
                insertSequence(result, small, big);
                big++;
                curSum += big;
            }
        }
        return result;
    }
};