和为s的连续整数序列

来自Leetcode面试题57-II 和为s的连续整数序列

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

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

示例 1：

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

---

滑动窗口

• 当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
• 当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
• 当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i 开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1开头的序列，所以窗口的左边界要向右移动

public int[][] findContinuousSequence(int target) {
    int left = 1; // 滑动窗口的左边界
    int right = 1; // 滑动窗口的右边界
    int sum = 0; // 滑动窗口中数字的和
    List<int[]> res = new ArrayList<>();

    while (left <= target / 2) {
        if (sum < target) {
            // 右边界向右移动
            sum += right;
            right++;
        } else if (sum > target) {
            // 左边界向右移动
            sum -= left;
            left++;
        } else {
            // 记录结果
            int[] arr = new int[right-left];
            for (int k = left; k < right; k++) {
                arr[k-left] = k;
            }
            res.add(arr);
            // 左边界向右移动
            sum -= left;
            left++;
        }
    }

    return res.toArray(new int[res.size()][]);
}