和为s的连续整数序列

一、需求

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

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

示例 1：

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

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

二、暴力法

 2.1  思路分析

1. 根据需求，我们要找一个连续的正整数序列，其和为target，那么我们可以在1 ~ target中找，即target = 9时，我们就在 1 2 3 4 5 6 7 8 9中寻找；
2. 因为题目要求序列长度至少为2，我们设置两个变量来控制这个序列的边界，令 i 指向序列的左边界，j 指向序列的右边界，如上例所示，当 i 指向4，就是左边界的最大值，j 指向的右边界的最大值 = i 指向左边界的最大值 + 1；
3. 故左边界的上界为 (target - 1) / 2，右边界的上界为 (target + 1) / 2；
4. 暴力法的思路就是在边界范围内，求出每一个连续正整数序列的和，使用 sum 来记录和，边求和边判断，①若 sum > target，说明当前以某位数为起点的连续整数和不符合要求，直接break，移动到该位数的下一位，比如移动到示例中 3 4 5 ，此时 sum = 12，直接退出进行下一轮，更新左边界为 4，②若 sum < target，j++，继续累加，③ 若sum == target，将当前的 [i，j ] 加入到数组中。退出循环，将数组加入到list中；

 2.2  代码实现

class Solution {
    public int[][] findContinuousSequence(int target) {
        //数组为引用类型
        List<int[]> list = new ArrayList<>();
        int iup = (target - 1) / 2;
        int jup = iup + 1;
        for(int i = 1; i <= iup; i++) {
            int j = i;
            int sum = 0;
            while(j <= jup) {
                sum += j;
                if(sum > target) {
                    break;
                } else if(sum < target) {
                    j++;
                } else {
                    int[] res = new int[j - i + 1];
                    for(int k = i; k <= j; k++) {
                        res[k-i] = k;
                    }
                    list.add(res);
                    break;
                }
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

2.3  复杂度分析

• 时间复杂度为，外层循环的时间复杂度为，内层最多为，故总体的时间复杂度为；
• 空间复杂度为为，除了答案数组之外，其余数组使用常数大小的额外空间；

三、滑动窗口(等差序列)

3.1  思路分析

1. 我们使用两个变量 lf ，rt 来来表示区间和sum的左右边界，因为是一个间隔为 1 的等差序列，故根据求和公式可得：；
2. 初始化lf = 1，rt = 2，当sum < target时，rt++，当sum > target时，lf++，当sum == target时，将区间内的数据存储到新数组中，并加入集合，当lf >= rt时，说明此时sum 会一直大于target，因此终止；
3. 该方法是对暴力法的优化，暴力法从每一个起点开始累加，然后判断，该方法使得区间的信息可以复用，比如 [ lf，rt ] 之间的sum==target时，那么下个区间 [ lf+1，rt ]就必然小于 target，暴力法会重新累加，而在这里会从 rt+1开始，即累加 [ lf+1，rt+1 ]；

3.2  代码实现

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

3.3  复杂度分析

• 时间复杂度为O(target)，两个指针的移动均单调不减，最多移动target次；
• 空间复杂度为O(1)；

四、滑动窗口(递增序列)

4.1  思路分析

1. 上一种方法用利用的是等差序列公式，若题目给定的只是一个递增序列，则需重新考虑解决办法；
2. 为了方便计算，我们选择滑动窗口的边界为前闭后开的方式，变量 i 指向左边界，变量 j 指向右边界，当sum < target时，扩大窗口范围，即更新sum，并j++，当sum < target时，缩小窗口范围，即更新sum，并i++，当sum == target时，存储 [ i , j )的元素到数组，并加入集合，然后更新sum，并i++；

4.2  代码实现

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        //规定窗口为前闭后开型
        int i = 1;
        int j = 1;
        int sum = 0;
        int limit = (target - 1) / 2;
        while(i <= limit) {
            if(sum < target) {
                sum += j;
                j++;
            } else if(sum > target) {
                sum -= i;
                i++;
            } else {
                int[] res = new int[j-i];
                for(int k = i; k < j; k++) {
                    res[k - i] = k;
                }
                list.add(res);
                sum -= i;
                i++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

4.3  复杂度分析

• 时间复杂度为O(target)；
• 空间复杂度为O(1)；

五、学习地址

作者：LeetCode官方

链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/mian-shi-ti-57-ii-he-wei-sde-lian-xu-zheng-shu-x-2/

作者：nettee

链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/

最后

以上就是难过饼干为你收集整理的和为s的连续整数序列的全部内容，希望文章能够帮你解决和为s的连续整数序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。