Leetcode 面试题57 - II.和为s的连续正数序列【C++】

本文最后更新于:2022年8月27日 晚上

地址:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

题目

输入一个正整数 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/2 + 1 ,例如对 target == 5 而言,最大只可能取到 5/2 +1 = 3 ,若取到4,由于题目要求是连续正整数,那么就必须取到3或者5,此时 3 + 4 = 7 已经大于目标值5。

这个题按照人的思维还是很容易想到的,就是从第一个正整数1开始往后依次相加,如果相加之后的和sum小于目标值,那就继续加后一个正整数,如果sum大于目标值,就减去序列最小的数,直到 sum == target 即找到了一组符合题目要求的连续正整数。

转化为编程思想,我首先想到了用队列queue来存储一串连续的正整数。队列中的数的和小于目标值,就将后一个正整数加入队列;如果大于目标值,就将队首的最小数弹出;直到队列中的数的和等于目标值target,此时逐个取出队列中的数即为一组符合题意的连续正整数。但是,使用队列只能很方便的用于找到一组这样的数,如果我们要继续找第二组,那就要让第一组数中从第二个数开始的所有数重新加入队列,这是很不划算的~

所以,还是用 vector<int>,与队列同样的步骤,但不需要每次找到一组连续整数后都重新将那些数加入到数组,每找到一个只需要利用 push_back() 函数,仅一条语句就可以将这个 vector<int> 加入到 vector<vector<int>> 的返回值中,然后就可以继续使用这个vector<int> 查找下一组满足题目要求的连续整数。

代码

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;//返回值
        vector<int> consecutive;//存储连续的数
        int sum = 0;//一串连续的数的和
        //最大可能取到的值是target/2+1
        //但当最后加上这个最大可能取到的数后,i也会++,所以应使 i <= target/2+2
        for (int i = 1; i <= target / 2 + 2;) {
            if (sum < target) {
                sum += i;
                consecutive.push_back(i);//将i加到一串连续的数的末尾
                i++;//取下一个整数
            }
            else if (sum == target) {
                ans.push_back(consecutive);
                sum -= consecutive[0];//减掉序列中最小的数
                consecutive.erase(consecutive.begin());//删去序列中最小的数
            }
            else {
                sum -= consecutive[0];//减掉序列中最小的数
                consecutive.erase(consecutive.begin());//删除第一个元素(最小的数)
            }
        }
        return ans;
    }
};

Leetcode 面试题57 - II.和为s的连续正数序列【C++】
https://mxy493.xyz/202003065179/
作者
mxy
发布于
2020年3月6日
许可协议