[数据结构与算法]剑指Offer57-Ⅱ—和为s的连续正数序列（java版）

题目描述：

标签：数学? 双指针? 枚举

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

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

代码：

?思路分析：

1、定义开始指针strat、结束指针end、以及当前和curSum

2、三种情况：

①curSum > target，说明需要curSum -= start；且start++

②curSum < target，说明需要end++，并且curSum += end

③curSum = target，说明要把start~end的元素加入到结果链表中

注意链表转换成二维数组的表示方法list.toArray(new int[n][])?

class Solution {
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> ret = new ArrayList<>();
        int start = 1;
        int end = 2;
        int curSum = 3;
        while(end < target){
            if(curSum > target){
                curSum -= start;
                start++;
            } else if(curSum < target){
                end++;
                curSum += end;
            }else{
                int cnt = 0;
                int[] list = new int[end - start + 1];
                for(int i = start;i <= end;i++){
                    list[cnt++] = i; 
                }
                ret.add(list);
                curSum -= start;
                start++;
                end++;
                curSum += end;
            }
        }
        
        return ret.toArray(new int[ret.size()][]);
    }
}