使用连续的自然数之和来表示一个整数(C卷)(简单题)

题目描述

一个整数可以由连续的自然数之和来表示。给定一个整数，计算该整数有几种连续自然数之和的表达式，且打印出每种表达式。

输入描述

一个目标整数T (1 <=T<= 1000)

输出描述

该整数的所有表达式和表达式的个数。如果有多种表达式，输出要求为：

1.自然数个数最少的表达式优先输出

2.每个表达式中按自然数递增的顺序输出，具体的格式参见样例。在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数。

举例如下:

输入:

18

输出:

18

3 4 5 6

5 6 7

题目分析

1. 首先就是两层for循环，依次相加数值直到满足给定值大小
2. 优化点在于，从数学的角度减少计算的次数，n < (n/2+n/2+1)

JAVA实现如下

 public static void compute(int n) {

        List<ArrayList<Integer>> result = new ArrayList<>();

        //初始化第一个List，值为n
        result.add(new ArrayList<Integer>() {{
            add(n);
        }});

        /**
         * 从数学的角度来说
         * n的组成数值不可能大于n/2+n%2,或者说n/2+1
         */
        for (int i = 1; i < n / 2 + n % 2; i++) {
            int tempSum = 0;
            boolean check = false;
            ArrayList<Integer> list = new ArrayList<>();

            for (int j = i; j <= n / 2 + n % 2; j++) {
                tempSum += j;
                list.add(j);
                //命中
                if (tempSum == n) {
                    check = true;
                    break;
                }

                if (tempSum > n) {
                    break;
                }
            }

            if (check) {
                result.add(list);
            }
        }

        //打印结果
        result.forEach(list -> {
            list.forEach(value -> System.out.print(value + " "));
            System.out.println();
        });

    }