和为s的连续正数序列

问题陈述

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

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

示例

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

思路分析

使用滑动窗口，i，j初始指向第一个元素，累计和，若小于target，j++；若大于target，i–；若相等，则存入一个array。具体见下。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class solution{
    public int[][] getContinueSequence(int target){
        int i=1,j=1,sum=0;
        List<int[]> list=new ArrayList<>();
        
        while(i<=target/2){
            //假设窗口左边界i=target/2, i+1=target/2 +1,那么i + (i+1) = target+1,即最小的窗口的元素之和就已经比target大了，所以当i>=target/2时不可能有一个窗口长度>=2的答案。
         if(sum<target){
             sum+=j;
             j++;
         } else if(sum>target){
             sum-=i;
             i++;
         } else{
            int[] arr=new int[j-i];
             for(int k=i;k<j;k++){
                 arr[k-i]=k; 
             }     
         }
            list.add(arr);
            sum-=i;//与上述i<=target/2相应，sum需减左边界值，继续下一轮判断。
            i++;
                
        }
        return list.toArray(new int[list.size()][]);//返回一个二维数组
    }

}