每日一题，提升自己。今天分享一道关于寻找连续序列的题目，且听我细细道来。

数组 - 寻找连续序列

1. 题目描述

        输入一个正整数 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

2. 解题思路

2.1 思路一

        要求一个数的连续序列和，首先可以得知一个数的连续序列和，其中序列中最小的数绝对不超过该数的的一半，这样遍历时就可以把起始数减少一半。从target/2开始进行遍历，作为起始数，然后开始下一个数字的累加。判断累加结果是否等于target，如果是则存入结果，起始数加一重新遍历。如果大于target则起始数加一重新遍历。如果小于target，末位数加一继续遍历。

        因为要求返回二维数组，而二维数组的长度是不确定的，内部的每一个一维数组的长度也是不确定的，所以每次初始化是一个List，然后每次得到满足条件的序列需要创建新得数组，将数组放进List中，最后返回时将List转换成二维数组即可。

2.2 思路二

此题最容易想到的思路就是暴力枚举，因为题目条件要求至少含有两个数，所以枚举到target/2即可停止，但是这种方法时间复杂度较高，虽然能通过，但是不是最优的。更好的方式是使用滑动窗口加指针来实现，设立左右指针，从开始维护一个子数组作为窗口，判断该窗口求和是否为target，如果是则将结果存入，因为此时的连续序列是一个公差为1的等差数列，所以窗口的求和可以使用等差数列求和来计算。，如果小于target则窗口右移，大于target则窗口左移。

复杂度：

• 时间复杂度：O(target)。滑动窗口最多位移target/2次。
• 空间复杂度：O(1)。排除必要的存储结果数组之外，只需要保存左右两个指针即可。

3. 算法流程

3.1 思路一流程

1. 首先初始起始数和末位数，start = 1,end = 2。
2. 当start<=target/2时，继续遍历。累积求和当前值，sum += start。
3. 枚举末位数，end=start+1开始，end<=taregt。求和sum += end。
4. 当sum == target，创建一个数组，长度为当前末位数减去起始数加一，然后把从起始数到末位数包括末位数遍历存入数组，再把该结果存入返回结果中。起始位加一重新遍历下一轮。
5. 当sum > target，起始数加一重新遍历。
6. 当sum < target，末位数加一继续遍历。

3.2 思路二流程

1. 首先初始化窗口，left=1 和 right=2。
2. 当 left < right 时始终维护该窗口，只有当到达边界位置时，窗口和 sum > target，left 始终右移，才会结束窗口维护。
3. 根据等差求和公式：和=(首项+尾)*项数 / 2，可得 sum = (left + right) * (right - left + 1) / 2sum=(left+right)∗(right−left+1)/2 可以直接算出滑动窗口和。
4. 当 sum == target 时，将窗口放入结果数组中。
5. 当 sum < target 时，说明窗口结果需要变大，right++。
6. 当 sum > target 时，说明窗口结果需要变小，left++。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static int[][] findContinuousSequence(int target) {
    List<int[]> res = new ArrayList<>();
    int start = 1,end = 2;
    while (start <= target/2){
        int n = start;
        for (end = start+1;end<=target;end++){
            n += end;
            if (n == target){
                int[] arr = new int[end-start+1];
                for (int i=0,j=start; j<=end; i++,j++){
                    arr[i] = j;
                }
                res.add(arr);
                start++;
                break;
            }
            if (n > target){
                start++;
                break;
            }
        }
    }
    return res.toArray(new int[res.size()][]);
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static int[][] findContinuousSequence(int target){
    List<int[]> res = new ArrayList<>();
    int left = 1,right=2;
    while (left<right){
        int sum = (left + right) * (right - left + 1) / 2;
        if (sum == target){
            int[] arr = new int[right-left+1];
            for (int i=0,j=left;j<=right;i++,j++){
                arr[i] = j;
            }
            res.add(arr);
            left++;
        }
        else if(sum > target){
            left++;
        }
        else {
            right++;
        }
    }
    return res.toArray(new int[res.size()][]);
}