面试题57-II.和为s的连续正数序列

1.题目

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

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

2.标准答案

枚举+暴力
枚举+数学优化
双指针

3.心得

由于面试完华为，最近有些松懈，好久没有做题，我拿到题第一眼是有点懵的。

关键点是要理解到，连续正数序列的和，其实是个差为1的等差数列的和。也就是说，只要知道这个等差数列的头和尾，就能知道这个数列的和，将其与s比较即可。

理解了关键点，接下来的思路就很多了。

首先是暴力枚举，枚举数列的头和尾即可。

其次我想到的是双指针法，因为最近面试刚手撕了三数之和，所以我第一时间想到了这种方法。

class Solution {

public:

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

        vector<vector<int>>vec;

        vector<int> res;

        for (int l = 1, r = 2; l < r;){

            int sum = (l + r) * (r - l + 1) / 2;

            if (sum == target){

                res.clear();

                for (int i = l; i <= r; ++i) res.emplace_back(i);

                vec.emplace_back(res);

                l++;

            }

            else if (sum < target) r++;

            else l++;

        }

        return vec;

    }

};

巴特西

面试题57-II.和为s的连续正数序列

面试题57-II.和为s的连续正数序列

1.题目

2.标准答案

3.心得

最新文章

热门文章