题目链接:

面试题57 - II. 和为s的连续正数序列

题目描述:

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

示例:

示例 1:

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

示例 2:

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

思路:

此题可考虑用滑动窗口解决。

leftright 分别表示窗口的左右边界,从 leftright 的序列和记为 sum

  • 如果 sum < target,则将右边界 right 右移,增大窗口囊括更多的元素以增大 sum
  • 如果 sum > target,则将左边界 left 右移,缩小窗口减少序列中的元素以减小 sum
  • 如果 sum == target,则此时的序列就是所求。

注意:窗口的左边界和右边界永远只能向右移动。
另外,左边界 left 移动到目标值 target 的一半处即可停止,因为当 left 移动到 target / 2 时,最小的序列和也大于 target 了,之后不会再有满足条件的。

代码实现:

class Solution {
    public int[][] findContinuousSequence(int target) {
        // 左边界,右边界
        int left = 1, right = 2;
        // 序列和
        int sum = left + right;
        // 存放结果
        List<int[]> result = new ArrayList<>();

        while (left <= target / 2 && left < right) {
            if (sum < target) {
                // 序列和小于目标值
                right ++;
                sum += right;
            } else if (sum > target) {
                // 序列和大于目标值
                sum -= left;
                left ++;
            } else {
                // 序列和等于目标值
                int[] arr = new int[right - left + 1];
                for (int i = left; i <= right; i++) {
                    arr[i - left] = i;
                }
                result.add(arr);
                sum -= left;
                left ++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

因为题目中已说明 target 是正整数序列和,且至少包含两个数,所以 target 至少是 3。