和为s的连续正数序列II

题目

输入一个正整数 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）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最简单的想法就是从1遍历到target/2的位置,多次遍历即可.

这里其实可以用到窗口滑动的方法.因为题目要求数字连续,就保证了窗口滑动可以确保所有的结果都适用

在领扣的提交中还有一位大神的解法,我将一位朋友的说明列在下面

一开始的时候，我考虑到了 target%i=0target 的时候，ii 是多少就有多少个元素在这个数组里面，但是我怎么也没想到把他们连在一起，而且我没法按照规律处理两个相邻的数字加在一起的情况。然后我看到了这段代码，豁然开朗，觉得有必要记录下来，感谢这位大哥。

这个题如果用滑动窗口，暴力方法去解决，是完全可以的，但是这道题的数学规律决定了他可以很快。

在这里，我们考虑以 99 为例子，99 可以被拆开成 4+54+5。

为了得到 44 我们需要思考一下。根据规律如果是 [4,5][4,5] 的话，i=2i=2，target % 2 = 0target 其中 [4,5][4,5] 可以改写成 4+(4+1)4+(4+1)。

在考虑三个元素的时候 2+3+42+3+4 我们发现他可以被写成 2+(2+1)+(2+2)2+(2+1)+(2+2) target%3 = 0target。似乎有点规律，我们不妨用 开始元素 xx 元素个数 你会发现如果 targettarget 刚好为这个值的话，也能满足 target%i=0target。

那我们如何让 targettarget 的值等于我们需要的值呢？

根据刚才的变式，我们发现只要让 targettarget 逐次减去 (1,2,3,....)(1,2,3,....) 并且当 target%i = 0target 的时候返回这个 target/itarget/i 就是我们需要的值了。

翻译成 Java，写在了下面：

作者：VaporMax
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/java-shuang-100-by-vapormax/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

暴力法

//最简单的想法就是从1遍历到target/2的位置,多次遍历即可.
//暴力法
int index = target % 2 == 1?target/2+1:target/2;
int num = 1;
ArrayList<int[]> result = new ArrayList<>();

while(num < index){
    int sum = 0;
    for(int i = num;i <= index;i++){
        sum += i;
        if(sum == target){
            int[] list = new int[i-num+1];
            for(int j = num,int n = 0;j < i+1;j++){
                list[n++] = j;
            }
            result.add(list);
            break;
        }
        if (sum > target){
            break;
        }
    }
    num++;
}
return result.toArray(new int[result.size()][]);

窗口滑动的方法

class Solution {
    public int[][] findContinuousSequence(int target) {
        //可以使用窗口滑动的方法
        //窗口的大小就是根据当前窗口的和与目标的对标.大了就缩小窗口,小了就扩大窗口,直到匹配
        int leftIndex = 1;
        int rightIndex = 1;
        int sum = 0;
        ArrayList<int[]> result = new ArrayList<>();
        while(leftIndex <= target /2){
            if(sum < target){
                sum += rightIndex;
                rightIndex++;
            }
            if(sum > target){
                sum -= leftIndex;
                leftIndex++;
            }
            if (sum == target){
                int[] ints = new int[rightIndex-leftIndex];
                for(int i = leftIndex;i < rightIndex;i++){
                    ints[i-leftIndex] = i;
                }
                result.add(ints);
                 sum -= leftIndex;
                leftIndex++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

大神的办法

class Solution {
    public int[][] findContinuousSequence(int target) {
        
        List<int[]> result = new ArrayList<>();
        int i = 1;

        while(target>0)
        {
            target -= i++;
            if(target>0 && target%i == 0)
            {
                int[] array = new int[i];
                for(int k = target/i, j = 0; k < target/i+i; k++,j++)
                {
                    array[j] = k;
                }
                result.add(array);
            }
        }
        Collections.reverse(result);
        return result.toArray(new int[0][]);       
    }
}

作者：VaporMax
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/java-shuang-100-by-vapormax/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。