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

Lin2J
2021-07-21 / 0 评论 / 165 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

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

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

解题思路:

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

$$ sum = \frac{(a+b) \times (b - a + 1)}{2} $$

使用双指针来解题,通过指针 $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)$:辅助变量占用常数大小的额外空间。