华为OD机试 - 用连续自然数之和来表达整数 - 滑动窗口（Java 2023 B卷 100分）

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

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

三、输出描述

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

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

每个表达式中按自然数递增的顺序输出，具体的格式参见样例。

在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数。

用例：

1、输入

9

2、输出

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

四、解题思路

1. 输入目标整数T；
2. 定义存储符合要求的数组集合arrList；
3. 定义sum，计算窗口之和；
4. 如果窗口之和大于目标t，left指针右移；
5. 如果窗口之和等于目标t，表示获取到合适窗口；
   • left指针右移，继续探索新窗口；
   • 如果right指针超出范围，break；
   • right指针右移，继续探索新窗口；
6. 如果窗口之和小于目标t，right指针右移；
7. 按照自然数个数升序排序，自然数个数最少的表达式优先输出；
8. 按照指定格式输出。

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 目标整数Tint t = sc.nextInt();int[] arr = new int[t];for (int i = 0; i < t; i++) {arr[i] = i + 1;}// 符合要求的数组集合List<int[]> arrList = new ArrayList<>();int left = 0;int right = 1;// 计算窗口之和int sum = arr[left];// 滑动窗口while (left < t) {// 如果窗口之和大于目标t，left指针右移if (sum > t) {sum -= arr[left++];} else if (sum == t) {// 如果窗口之和等于目标t，表示获取到合适窗口int[] oks = Arrays.copyOfRange(arr, left, right);arrList.add(oks);// left指针右移，继续探索新窗口sum -= arr[left++];// 如果right指针超出范围，breakif (right >= t) {break;}// right指针右移，继续探索新窗口sum += arr[right++];} else {// 如果窗口之和小于目标t，right指针右移sum += arr[right++];}}// 按照自然数个数升序排序，自然数个数最少的表达式优先输出arrList.sort((x, y) -> x.length - y.length);// 按照指定格式输出for (int[] array : arrList) {StringJoiner stringJoiner = new StringJoiner("+");for (int i : array) {stringJoiner.add(String.valueOf(i));}System.out.println(t + "=" + stringJoiner);}System.out.println("Result:" + arrList.size());
}

六、效果展示

1、输入

100

2、输出

100=100
100=18+19+20+21+22
100=9+10+11+12+13+14+15+16
Result:3

🏆下一篇：华为OD机试 - 荒岛求生 - 栈Stack（Java 2023 B卷 100分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。