《剑指offer》面试题57 - II. 和为s的连续正数序列

问题描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9

输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

 

限制：

1 <= target <= 10^5

代码

如果\(target\)要分解为两个连续的正数和，因为这两个数只相差\(1\)，则\((target - 1)\%2==0\),并且正数的第一个元素是\((target-1)/2\).
如果\(target\)要分解为三个连续的正数和，因为这三个数相差\(1，2\)，则\((target - 1 - 2)\%3==0\),并且正数的第一个元素是\((target-1-2)/3\)
\(\dots\)

class Solution {

public:

    vector<vector<int>> findContinuousSequence(int target) {

        vector<vector<int>> ans;

        int i = 1,j;

        while(target > 0)

        {

            target -= i;

            if(target > 0&& (target) % (i+1) == 0)

            {

                vector<int> tmp;

                for(j = 0; j <= i; ++j)

                    tmp.push_back((target)/(i+1)+j);

                ans.push_back(tmp);

            }

            ++i;

        }

        reverse(ans.begin(),ans.end());

        return ans;

    }

};

结果：

执行用时 :4 ms, 在所有 C++ 提交中击败了84.28%的用户

内存消耗 :6.9 MB, 在所有 C++ 提交中击败了100.00%的用户

巴特西

《剑指offer》面试题57 - II. 和为s的连续正数序列

问题描述

代码

最新文章

热门文章