描述

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。(至少包括两个数)

示例：

• 输入：9
• 输出：[[2,3,4],[4,5]]

思路1：暴力破解

假设每个数都可能是连续序列的第一个数，计算每个连续区间

由于至少包括两个数，因此可以移动到sum/2即可，后面的序列一定大于sum，减少循环次数

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        for(int i = 1; i <= sum / 2; i++) {
            //使用tmp保存区间和
            int tmp = i;
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            for(int j = i + 1; j < sum; j++) {
                tmp += j;
                list.add(j);
                if(tmp == sum) {
                    ret.add(list);
                    break;
                }
                if(tmp > sum) {
                    break;
                }
            }
        }
        return ret;
    }
}

思路2：队列+滑动窗口

思路1中需要重复计算，例如从1开始的区间1+2+3+4，从2开始的区间2+3+4。重复计算了2+3+4

可以使用队列存储区间元素，超出sum，移除队头元素，计算下一个区间，从5开始累加。

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Deque<Integer> dueue = new LinkedList<>();
        int tmp = 1;
        dueue.offer(1);
        for(int i = 1; i <= sum / 2; i++) {
            //第一次循环计算从1开始的区间，1+2+3+4
            //第二次循环计算从2开始的区间，2+3+4
            //第三次循环计算从3开始的区间，从5开始累加
            int j = dueue.peekLast() + 1;
            while(true) {
                if(tmp == sum) {
                    ret.add(new ArrayList<>(dueue));
                    tmp -= dueue.poll();
                    break;
                } else if(tmp > sum) {
                    tmp -= dueue.poll();
                    break;
                } else {
                    dueue.offer(j);
                    tmp += j;
                }
                j++;
            }
        }
        return ret;
    }
}

优化：i表示区间的右边界

1. 当区间和<sum时，扩大右边界
2. 当区间和>=sum时，右边界不动，移除队头元素

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int tmp = 0;
        int i = 1;
        //这里需要多两次循环
        while(i <= (sum / 2) + 2) {
            if(tmp < sum) {
                queue.offer(i);
                tmp += i;
                i++;
            } else if(tmp > sum) {
                tmp = tmp - queue.poll();
            } else {
                if(queue.size() > 1) {
                    ret.add(new ArrayList<>(queue));
                }
                tmp = tmp - queue.poll();
            }
        }
        return ret;
    }
}

思路3：双指针+滑动窗口

1. 双指针从头开始移动
2. 当窗口内的和大于sum，缩小左边界
3. 当窗口内的和小于sum，扩大右边界

写法1：双指针+求和公式

求和公式：(首+尾)*个数/2

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        int left = 1;
        int right = 2;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        while(left <= sum / 2) {
            //使用求和公式
            int n = (left + right) * (right - left + 1) / 2;
            if(n < sum) {
                right++;
            } else if(n > sum) {
                left++;
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = left; i <= right; i++) {
                    list.add(i);
                }
                ret.add(list);
                //缩小窗口
                left++;
            }
        }
        return ret;
    }
}

写法2：双指针+前缀和

使用tmp保存计算过的和，窗口缩小时和减小，窗口增大时和增加

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        int left = 1;
        int right = 2;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int tmp = 3;
        while(left <= sum / 2) {
            if(tmp < sum) {
                right++;
                tmp += right;
            } else if(tmp > sum) {
                tmp -= left;
                left++;
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = left; i <= right; i++) {
                    list.add(i);
                }
                ret.add(list);
                tmp -= left;
                left++;
            }
        }
        return ret;
    }
}