题目描述

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

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

题解

借用上一题的思想，还是使用双指针，只是这里的指针代表的不是数组下标，而是数字。开始时把left初始化为1，right初始化为2。题目连续正数列的性质，可以使用求和公式求序列和：

有一个地方要注意，正数序列的第一个数不可能超过s的一半，将这个条件加入循环条件避免多余的运算。

• 如果序列和小于sum，则扩大序列的范围，即right++；
• 如果序列和大于sum，则缩小序列的范围，即left+；
• 如果序列和等于sum，则找到一个结果。然后扩大序列的范围，即right++。

下面是参考代码：

class Solution {
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> resArr = new ArrayList<>();
        int left = 1, right = 2;
        while (left < right && left <= target/2) {
            int curSum = (left + right) * (right - left + 1) / 2;
            if (curSum < target) {
                right++;
            } else if (curSum > target) {
                left++;
            } else {
                int[] temp = new int[right - left + 1];
                int begin = left;
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = begin++;
                }
                resArr.add(temp);
                left++;
            }
        }
        int[][] res = new int[resArr.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = resArr.get(i);
        }
        return res;
    }
}