华为od（D卷） 用连续自然数之和来表达整数

题目描述

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

输入描述

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

输出描述

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

示例1

输入
9

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

示例2

输入
10

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

思路

滑动窗口

代码

public class Demo18 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();System.out.println("Result:" + window(n));}in.close();}public static int window(int n) {// 左闭右闭int left = 1;int sum = 0;List<List<Integer>> res = new ArrayList<>();for (int right = 1; right <= n; right++) {sum += right;while (sum > n) {sum -= left;left++;}if (sum == n) {List<Integer> a = new ArrayList<>();for (int i = left; i <= right; i++) {a.add(i);}res.add(a);sum -= left;left++;}}Collections.reverse(res);for (List<Integer> re : res) {String collect = re.stream().map(String::valueOf).collect(Collectors.joining("+"));System.out.println(n + "=" + collect);}return res.size();}
}