剑指 Offer 57 - II: 和为s的连续正数序列

[songyy5517]

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

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

示例 1：

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

示例 2：

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

分析 这道题需要求连续正数序列的和。考虑到连续这个性质，我们可以使用双指针实现滑动窗口模拟序列的变化过程。初始状态下将窗口设为[1, 2]，当窗口和小于sum时，扩充窗口的右边界；当窗口和大于或等于sum时，收缩窗口的左边界。当窗口大小为1时，停止操作。

[songyy5517]

思路：双指针 & 滑动窗口

1. 异常处理；
2. 定义前后双指针分别指向1和2；
3. 当两指针没有相遇时，循环计算指针范围内元素之和，根据target与元素之和的关系调整指针： （1）若等于target，则将窗口内的元素保存起来（到列表）； （2）若大于等于target，则将前指针向后移动一格； （3）若小于target，则将后指针向后移动一格；
4. 将列表转换成二维数组并返回。

复杂度分析

• 时间复杂度： $O(N)$ ，N为target，窗口的最终状态为[n/2, n/2]，两指针移动的次数之和为N；
• 空间复杂度： $O(\sqrt{N})$ ，额外定义了双指针和数组列表；设满足条件的序列为 $m + (m + 1) + ... + (m + p) = n$ ，即 $(p + m)^2 = 2N + m^2$ ，数组列表的大小 $p = \sqrt{m^2 + 2N} - m = O(\sqrt{N})$ 。

[songyy5517]

class Solution {
    public int[][] findContinuousSequence(int target) {
        // 思路：双指针滑动窗口
        // 1. 异常处理
        if (target <= 2)
            return new int[0][0];

        // 2. 定义相关变量
        ArrayList<int[]> record = new ArrayList();  // ！数组列表的定义方式
        int start_1 = 1, start_2 = 2, sum = 3;  // ！sum可优化

        while(start_1 < start_2){
            if (sum == target){
                int[] res = new int[start_2 - start_1 + 1];
                for (int i = 0; i < res.length; i++)
                    res[i] = start_1 + i;
                record.add(res);
            }

            if (sum >= target){  // 合并等于的情况
                sum -= start_1;
                start_1 ++;
            }
            else {
                start_2 ++;
                sum += start_2;
            }
        }

        // 3. 返回结果
        return record.toArray(new int[record.size()][]);  // ！从列表转换成数组
    }
}

[songyy5517]

Key points

1. 数组列表的定义方式
2. 从列表转换成数组
3. sum优化
4. 合并等于的情况

2024/3/15

• 初始状态下的窗口。

2024/3/16

• 复杂度分析