57.2 和为 S 的连续正数序列

题目链接

Leetcode

题目描述

输出所有和为 S 的连续正数序列。例如和为 100 的连续序列有：

[9, 10, 11, 12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]

解题思路

用滑动窗口 start～end 表示当前的连续正数序列，curSum 为它们的和：和小于 target 时 end 右移扩大窗口，大于 target 时 start 右移缩小窗口，等于时记录结果，再把窗口整体右移一格继续查找。start 和 end 都只增不减，时间复杂度为 O(target)。

例如 target = 9 时，窗口依次为 1～2、1～3、1～4（和为 10）、2～4（和为 9，记录）、3～5（和为 12）、4～5（和为 9，记录）……end 到达 target 时结束，结果为 [2, 3, 4] 和 [4, 5]。

public int[][] fileCombination(int target) {
    List<int[]> ret = new ArrayList<>();
    int start = 1, end = 2;
    int curSum = 3;
    while (end < target) {
        if (curSum > target) {
            curSum -= start;
            start++;
        } else if (curSum < target) {
            end++;
            curSum += end;
        } else {
            int[] arr = new int[end - start + 1];
            for (int i = start; i <= end; i++) {
                arr[i - start] = i;
            }
            ret.add(arr);
            curSum -= start;
            start++;
            end++;
            curSum += end;
        }
    }
    return ret.toArray(new int[ret.size()][]);
}