[NC]256. 和为 s 的连续正数序列

🚩传送门：牛客题目
力扣题目

题目

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

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

示例 1：

输入：target = 9 输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

解题思路：滑动窗口 [ 双指针 ]

设连续正整数序列的左边界 和右边界 ，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内元素和与目标值 的大小关系

• 若相等则记录结果
• 若大于 则移动左边界 （以减小窗口内的元素和）
• 若小于 则移动右边界 （以增大窗口内的元素和）

复杂度分析

时间复杂度：，其中 为数组长度，两个指针移动的总次数最多为 次

空间复杂度：，使用常数大小的额外空间。

官方代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2;
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            int sum = (i + j) * (j - i + 1) / 2;
            if (sum == target) {
                int[] ans = new int[j - i + 1];
                for (int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if (sum > target) i++;
            else j++;
        }
        return res.toArray(new int[0][]);
    }
}