和为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 <= target <= 10^5

题目链接

Leetcode

题目解答

解法一

比较容易想到的解法就是枚举+暴力，就是从第一个元素开始累加，如果累加和与target相等则把和清零，换到下一个元素作为起始值累计，由于累加的元素至少要有2个，而且和不会超过target，所以只需要枚举到中间位置target/2+1即可。

时间复杂度:$O(n\sqrt{n})$ 空间复杂度:$O(1)$

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

执行用时：8 ms, 在所有 Java 提交中击败了13.15%的用户
内存消耗：36.5 MB, 在所有 Java 提交中击败了78.21%的用户

解法二

因为是求连续的元素和，可以借助求和公式简化运算，使用双指针根据条件判断向右移动，在解法一的基础之上，更加充分的利用已知信息来优化时间效率，当区间[left,right]累加和为target的时侯，必然有[left+1,right]累加和小于target，这种情况下就可以直接把right后移一位，从而避免重复计算。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

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

执行用时：4 ms, 在所有 Java 提交中击败了58.34%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了90.87%的用户

解法三

借助滑动窗口的思想，当累加和小于target的时侯，右窗口扩大1位，当累加和大于target的时侯，左窗口缩小1位，窗口滑动的最大距离为target/2+1，求和的过程只用到了简单运算，相较于解法二，解法三在时间效率上得到了更进一步的提升。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 2, sum = 3, limit = (target >> 1) + 1;
        List<int[]> res = new ArrayList<>();
        while (left < limit) {
            if (sum < target) {
                right++;
                sum += right;
            } else {
                if (sum == target) {
                    int[] arr = new int[right - left + 1];
                    for (int i = 0; i < arr.length; i++) {
                        arr[i] = left + i;
                    }
                    res.add(arr);
                }
                sum -= left;
                left++;
            }
        }
        return res.toArray(new int[0][]);
    }
}

执行用时：2 ms, 在所有 Java 提交中击败了97.59%的用户
内存消耗：36.8 MB, 在所有 Java 提交中击败了15.95%的用户