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

题目描述

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

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

输入输出

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

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

基本思路

  1. 初始化： 左边界 i = 1 ，右边界 j = 2 ，元素和 s = 3 ，结果列表 res ；

  2. 循环： 当 i >= j 时跳出；

    • 当 s > target 时： 向右移动左边界 i = i + 1 ，并更新元素和 s ；

    • 当 s < target 时： 向右移动右边界 j = j + 1 ，并更新元素和 s ；

    • 当 s = target 时： 记录连续整数序列，并向右移动左边界 i = i + 1 ；

  3. 返回值： 返回结果列表 res ；

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j){
            if(s == target){
                int[] ans = new int[j-i+1];
                for(int k = i; k <= j; k++){
                    ans[k-i] = k;
                }
                res.add(ans);
            }
            if(s >= target){
                s -= i;
                i++;
            }
            else if(s < target){
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}