剑指offer-42-和为s的连续整数序列

思路

• 滑动窗口，用一个sumt记录一个队列中的和，如何sumt>sum,出队，sumt-=queue.poll(),小于sum，则入队
• 求数组区间和就用前缀和，前缀和数组。然后求前缀和两个元素的差，感觉还是用滑动窗口啊。QAQ

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> arr=new ArrayList<>();
        int p=0,q=0,sumt=0;
        Queue<Integer> queue=new LinkedList<>();
        while(p<=q &&q<sum){
            if(sumt<sum){
                q++;
                queue.add(q);
                sumt+=q;
            }else if(sumt>sum){
                p++;
                sumt-=queue.poll();
            }else{
                arr.add(new ArrayList<>(queue));
                p++;
                sumt-=queue.poll();
            }
        }
        return arr;
    }
}