剑指 Offer——和为 S 的连续正数序列

1. 题目

2. 解答

定义两个指针，刚开始分别指向 1 和 2，求出位于这两个指针之间的元素和。如果和大于 S，前面的指针向后移直到和不大于 S 为止；反之，如果和等于 S，则此时两个指针之间的元素序列即为一个所求的结果，后面的指针向后移动。

第一个指针的范围为 \([1, \frac{S+1}{2})\)，左闭右开，可举一个奇数偶数的例子即可知。时间复杂度为 \(O(n)\)。

class Solution {

public:

    vector<vector<int> > FindContinuousSequence(int sum) {

        int middle = (sum + 1) / 2;

        int small = 1;

        int big = 2;

        int target = small + big;

        vector<vector<int> > result;

        while (small < middle)

        {

            if (target > sum)

            {

                while (small < middle && target > sum)

                {

                    target -= small;

                    small++;

                }

            }

            else

            {

                if (target == sum)    Add_Sequence(result, small, big);

                big++;

                target += big;

            }

        }

        return result;

    }

    void Add_Sequence(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);

    }

};

获取更多精彩，请关注「seniusen」!

巴特西

剑指 Offer——和为 S 的连续正数序列

1. 题目

2. 解答

最新文章

热门文章