LeetCode面试题57:和为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,2,3,4…，暴力解法以1开头进行计算，然后以2开头进行计算。。。这里就不说这种方法了；
数组问题可以尝试使用滑动窗口解决，这里规定滑动窗口是左闭右开的[i,j),
i=1,j=1，这里的循环判断条件是i<=target/2,这个也好理解，例如target=9，当i=5时，后面没有数字可以满足加上i等于target；
定义一个sum代表数字和
如果sum<target,窗口要扩大,j向后移动;
如果sum>target，窗口要缩小，i向后移动;
如果sum==target,读取窗口内的数据，sum-=i,i向后移动

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>>res;
        if(target==0)
        {
            return res;
        }
        int i=1;
        int j=1;
        int sum=0;
        while(i<=target/2)
        {
            if(sum<target)
            {
                
                sum+=j;
                j++;
            }
            else if(sum>target)
            {
                sum-=i;
                i++;
            }
            else
            {
                vector<int>arr;
                for(int k=i;k<j;k++)
                {
                    arr.push_back(k);
                }
                res.push_back(arr);
                sum-=i;
                i++;
            }
        }
       return res;
    }
};

最后

以上就是无心可乐最近收集整理的关于LeetCode面试题57:和为s的连续正数序列的全部内容，更多相关LeetCode面试题57:和为s内容请搜索靠谱客的其他文章。