40 输入一个正数s，打印出所有和为s 的连续正数序列（至少两个数）。

100 阅读 0 评论 66 点赞

我是靠谱客的博主悦耳黑裤，这篇文章主要介绍40 输入一个正数s，打印出所有和为s 的连续正数序列（至少两个数）。，现在分享给大家，希望可以做个参考。

一、题目
输入一个正数s，打印出所有和为s 的连续正数序列（至少两个数）。
举例说明

例如输入15，由于1+2+3+4+5=4＋5+6＝7+8=15，所以结果打出3 个连续序列1～5、4～6 和7～8。

二、解题思路
考虑用两个数small 和big 分别表示序列的最小值和最大值。首先把small 初始化为1, big 初始化为2。如果从small 到big 的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small 的值。如果从small 到big 的序列的和小于s，我们可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small 到(1+s)/2 为止。
以求和为9 的所有连续序列为例，我们先把small 初始化为1, big 初始化为2。此时介于small 和big 之间的序列是｛1，2}，序列的和为3，小于9，所以我们下一步要让序列包含更多的数字。我们把big 增加1 变成3,此时序列为{1，2，3}。由于序列的和是6，仍然小于9，我们接下来再增加big 变成4，介于small 和big 之间的序列也随之变成｛ l, 2, 3, 4｝。由于列的和10 大于9，我们要删去去序列中的一些数字，于是我们增加small 变成2，此时得到的序列是｛2, 3, 4｝，序列的和E好是9。我们找到了第一个和为9 的连续序列，把它打印出来。接下来我们再增加big，重复前面的过程，可以找到第二个和为9 的连续序列｛4，5}。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static List<List<Integer>> findContinuousSequence(int sum) {
    List<List<Integer>> result = new ArrayList<>();
    if (sum < 3) {
        return result;
    }

    int small = 1;
    int big = 2;
    int middle = (1 + sum) / 2;
    int curSum = small + big;

    while (small < middle) {
        if (curSum == sum) {
            List<Integer> list = new ArrayList<>(2);
            for (int i = small; i <= big; i++) {
                list.add(i);
            }
            result.add(list);
        }

        while (curSum > sum && small < middle) {
            curSum -= small;
            small++;

            if (curSum == sum) {
                List<Integer> list = new ArrayList<>(2);
                for (int i = small; i <= big; i++) {
                    list.add(i);
                }
                result.add(list);
            }
        }

        big++;
        curSum += big;
    }

    return result;
}

调用:

复制代码

1
2
3
4
5
6
7
8
9
10
11
   List<List<Integer>> continuousSequence = findContinuousSequence(15);
        for(int i = 0; i < continuousSequence.size(); i++) {
            List<Integer> integers = continuousSequence.get(i);
            for(int j = 0; j < integers.size(); j++) {
                System.out.print(integers.get(j));

            }
            System.out.println();

        }

打印结果

复制代码