57-Ⅱ 和为s的连续正数序列

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

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路：

求一段连续正数序列的和的公式，假设最小数为 $a$，最大数为 $b$，则这段数字的和为：

使用双指针来解题，通过指针 $l$ 和 $r$ ，不断计算 $[l, r]$ 窗口的序列和 $sum$，根据 $sum$ 的大小调整窗口的大小。

• 如果 $sum = target$，说明这段序列和合法，可以记录起来，同时缩小窗口，$l$ 自增；
• 如果 $sum > target$，说明窗口太大，$l$ 自增；
• 如果 $sum < target$，说明窗口太小，$r$ 自增；

代码：

public int[][] findContinuousSequence(int target) {
    List<int[]> ans = new ArrayList<>();
    for (int l = 1, r = 2; l < r; ) {
        int sum = (l + r) * (r - l + 1) / 2;
        if (sum == target) {
            int[] list = new int[r - l + 1];
            for (int i = l; i <= r; i++) {
                list[i - l] = i;
            }
            ans.add(list);
            l++;
        } else if (sum < target) {
            r++;
        } else {
            l++;
        }
    }
    return ans.toArray(new int[ans.size()][]);
}

复杂度分析：

• 时间复杂度$O(N)$：其中 $N = target$，$l$ 和 $r$ 最终会相遇在 $\frac{N}{2}$ 的位置。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。