华为OD机试-整数分解

题目描述

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

输入描述

一个目标整数t，1 <= t <= 1000

输出描述

1. 该整数的所有表达式和表达式的个数。如果有多种表达式，自然数个数最少的表达式优先输出
2. 每个表达式中按自然数递增输出，具体的格式参见样例。在每个测试数据结束时，输出一行Result:X，其中X是最终的表达式个数。

示例一

输入：

9

输出：

9=9
9=4+5
9=2+3+4
Result:3

说明：

整数9有三种表达方法

示例二

输入：

10

输出：

10=10
10=1+2+3+4
Result:2

Java代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int t = scanner.nextInt();
    solution(t);
  }

  private static void solution(int t) {
    System.out.println(t + "=" + t);
    List<String> res = new ArrayList<>();
    for (int n = 1; n < t; n++) {
      int sum = 0;
      StringBuilder builder = new StringBuilder();
      for (int i = n; sum < t; i++) {
        sum += i;
        if (sum == t) {
          builder.append(i);
          res.add(t + "=" + builder);
          break;
        }
        builder.append(i)
            .append("+");
      }
    }
    res.sort(Comparator.comparingInt(String::length));
    res.forEach(System.out::println);

    System.out.println("Result:" + (res.size() + 1));
  }
}