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;
        }
    }
}

//优化版本