入口

力扣https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

題目描述

輸入一個正整數 target ，輸出所有和為 target 的連續正整數序列（至少含有兩個數）。

序列內的數字由小到大排列，不同序列按照首個數字從小到大排列。

 

示例 1：

        輸入：target = 9
        輸出：[[2,3,4],[4,5]]
示例 2：

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

限制：

        1 <= target <= 10^5

方法一：滑動窗口

        解題思路： 用兩個指針代表窗口的左右邊界，指針移動代表窗口滑動，記錄窗口內的數字和sum，窗口滑動同時更改sum。

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1;//左指針
        int j = 1;//右指針
        int sum = 0;
        List<int[]> res = new ArrayList<>();
        while(i <= target/2){
            if(sum < target){
                //和小,右邊界右移
                sum+=j;
                j++;
            }else if(sum > target){
                //左邊界右移
                sum-=i;
                i++;
            }else{
                //記錄結果
                int[] arr = new int[j-i];
                for(int z = i;z < j;z++){
                    arr[z-i] = z;
                }
                res.add(arr);
                //左邊界右移
                sum -= i;
                i++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}