package leetcode;

import edu.princeton.cs.algs4.Cycle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

public class FirstDay {

public static void main(String\[\] args) {  
    int\[\]\[\] i = findContinuousSequence(15);  
    Arrays.stream(i).forEach(new Consumer<int\[\]>() {  
        @Override  
        public void accept(int\[\] ints) {  
            Arrays.stream(ints).forEach(i->System.out.println(i));  
            System.out.println("\_\_\_\_\_\_\_\_\_\_\_\_\_\_");  
        }  
    });  
}  

/\*\*  
 \* 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。  
 \* 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。  
 \*/  
public static int\[\]\[\] findContinuousSequence(int target) {  
    List<int\[\]> result = new ArrayList<>();  
    if (target == 0 || target == 1 || target == 2) {  
        return new int\[0\]\[0\];  
    }  
    CycleQueun cq = new CycleQueun();  
    int mid =target/2+1;  
    for (int i = mid; i >0 ; i--) {  
        int m = cq.addQ(i);  
        if(m == target){  
            int\[\] resu= cq.getQ();  
            result.add(resu);  
        }  
        if(m>target){  
            int sum = cq.removeQ();  
            if(m == target){  
                int\[\] resu= cq.getQ();  
                result.add(resu);  
            }  
        }  
    }  
    int\[\]\[\] results = new int\[result.size()\]\[\];  
    for (int i = 0; i <result.size() ; i++) {  
        results\[i\]=result.get(i);  
    }  
    return revse(results);  
}  
public static int\[\]\[\] revse(int\[\]\[\] objs){  
    for (int i = 0 ,j = objs.length-1; i<j; i++,j--) {  
        int\[\] Oi = objs\[i\];  
        int\[\] Oj = objs\[j\];  
        objs\[i\] = Oj;  
        objs\[j\] = Oi;  
    }  
    return objs;  
}  
static class CycleQueun{  
    private int sum;  
    private List<Integer> q = new LinkedList<>();  
    public int addQ(int a){  
        sum += a;  
        q.add(a);  
        return sum;  
    }  
    public int removeQ(){  
        int i = q.get(0);  
        sum -= i;  
        q.remove(0);  
        return sum;  
    }  
    public int\[\] getQ(){  
        int\[\] result = new int\[q.size()\];  
        for (int i = 0; i <q.size() ; i++) {  
            result\[i\]=q.get(i);  
        }  
        for (int i = 0 ,j = result.length-1; i<j; i++,j--) {  
            int Oi = result\[i\];  
            int Oj = result\[j\];  
            result\[i\] = Oj;  
            result\[j\] = Oi;  
        }  
        return result;  
    }  
}  

}

//优化版本

class Solution {

    public int[][] findContinuousSequence(int target) {

        List result = new ArrayList<>();

        int mid = target/2+1;

        int i =1, j =1;

        int sum = 0;

        while(j<=mid){

            sum = (i+j)*(j-i+1)/2;

            if(sum == target){

                int[] res = new int[j-i+1];

                for (int k = 0; k <= j-i; k++) {

                    res[k] = i+k;

                }

                i++;j++;

                result.add(res);

            }

            if(sum < target){

                j++;

            }

            if(sum>target){

                i++;

            }

        }

        int[][] results = new int[result.size()][];

        for (int z= 0; z <result.size() ; z++) {

            results[z]=result.get(z);

        }

        return results;

    }

}