剑指Offer【和为s的连续正数序列】

题目描述

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

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

示例 1：

1 2	`输入：target = 9 输出：[[2,3,4],[4,5]]`

示例 2：

1 2	`输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]`

限制：

1 <= target <= 10^5

解法

滑动窗口
- 套滑动窗口模板，l是窗口左边界，r是窗口右边界，窗口中的值一定是连续值。
- 当窗口中数字和小于target时，r右移; 大于target时，l右移; 等于target时就获得了一个解
- 答案中会出现的最大数字(target+1)/2

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res=new ArrayList<>();
        int left=1;
        int right=2;
        int maxNum=(target+1)/2;//答案会出现的最最大数字
        int tmpSum=left+right;
        //开始滑动,条件是窗口内的最大值小于等于答案会出现的最大值
        while (right<=maxNum){
            //1.当窗口内的和值小于目标值
            if (tmpSum<target){
                //右区间右移
                right++;
                tmpSum+=right;
            }
            //2.当前窗口内的大于等于目标值
            else if (tmpSum>target){
                //左区间右移
                tmpSum-=left;
                left++;
            }
            //3.当前窗口内的和等于目标值
            else{
                //记录当前的结果加入结果集
                int innerLen=right-left+1;
                int []temRes=new int[innerLen];
                for (int i = 0; i < innerLen; i++) {
                    temRes[i]=left+i;
                }
                res.add(temRes);
                //加完后窗口右移
                left++;
                right++;
                tmpSum+=innerLen;
            }
        }
        int[][] realRes=new int[res.size()][];
        return res.toArray(realRes);
    }
}