华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0~N的箱子，每个箱子上面贴有一个数字。
阿里巴巴牢记出一个咒语数字k(k<N)，找出连续k个宝箱数字和的最大值，并输出该最大值。
二、输入描述
第一行输入一个数字字符串，数字之间使用逗号分隔，例如：2,10,-3,-8,40,5
• 1 ≤ 字串中数字的个数 ≤ 100000
• -10000 ≤ 每个数字 ≤ 10000
第二行输入咒语数字，例如：4，咒语数字大小小于宝箱的个数
三、输出描述
连续k个宝箱数字和的最大值，例如：39
四、测试用例
测试用例1：
1、输入
2,10,-3,-8,40,5
4
2、输出
39
3、说明
初始窗口为 2,10,-3,-8，和为 1。
移动窗口，接下来是 10,-3,-8,40，和为 39，更新最大和。
接下来窗口为 -3,-8,40,5，和为 34，保持最大和为 39。
测试用例2：
1、输入
8
1
2、输出
8
3、说明
只有一个数字，窗口大小为 1，直接输出该数字 8。
测试用例3：
1、输入
-1,-2,-3,-4
2
2、输出
-3
3、说明
初始窗口为 -1,-2，和为 -3。
后续窗口的和分别为 -5 和 -7，因此最大和保持为 -3。
五、解题思路
1、为什么采用滑动窗口？
在这个问题中，我们需要找到一组连续的 k 个数字的最大和。直接采用暴力算法虽然可以解决问题，但其时间复杂度较高，尤其是在数组较大时，效率会非常低下。
滑动窗口技术特别适合以下几种场景：
- 连续子数组或子序列问题：滑动窗口通常用来解决连续的子数组或子序列的问题，比如本题中要求连续的 k 个数字的和。
- 窗口大小固定：滑动窗口适用于固定窗口大小的场景，比如本题中，我们始终需要比较连续 k 个数字的和。
如果采用暴力解法，我们可以尝试遍历数组中每一个可能的长度为 k 的子数组，然后计算其和并与当前最大和进行比较。这种方法的复杂度是 O(N * k)，其中 N 是数组的长度。对于每一个可能的起点，我们都需要重新计算一遍 k 个数字的和，这样在处理大量数据时会非常耗时。
2、滑动窗口如何提升效率？
滑动窗口通过复用前一次的计算结果，减少了重复计算。具体来说，滑动窗口的做法是：
- 计算第一个窗口的和。
- 之后的每一个窗口，都可以通过从当前窗口的和中减去左边的元素，并加上右边的新元素来更新，而不需要重新计算整个窗口的和。
滑动窗口算法只需要遍历数组一次，时间复杂度是 O(N)，这显著提高了效率。
3、具体步骤：
这个问题属于经典的“滑动窗口”问题。我们需要找到给定数组中连续 k 个数字的最大和，滑动窗口算法非常适合这种问题。
解题思路如下：
- 初始化窗口：首先计算前 k 个数字的和，作为初始窗口的和。
- 滑动窗口遍历数组：从 k 开始，逐步向右移动窗口，每次移动时，去掉窗口最左边的元素，加入窗口最右边的元素。这样，我们就可以通过简单的加减操作更新窗口的和，而不需要重复计算整个窗口。
- 记录最大和：在每次滑动窗口时，比较当前窗口的和和最大和，保留较大者。
- 返回结果：最后输出最大和。
六、Java算法源码
public class OdTest01 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入的数字字符串并分割成整数数组String[] numStr = scanner.nextLine().split(",");int[] nums = new int[numStr.length];for (int i = 0; i < numStr.length; i++) {nums[i] = Integer.parseInt(numStr[i]); // 将字符串数组转为整数数组}// 读取咒语数字kint k = scanner.nextInt();// 调用计算最大连续k个数的和的函数System.out.println(maxSum(nums, k));}// 计算最大连续k个宝箱数字和public static int maxSum(int[] nums, int k) {int n = nums.length;// 初始化第一个窗口的和int currentSum = 0;for (int i = 0; i < k; i++) {currentSum += nums[i]; // 计算第一个窗口的和}int maxSum = currentSum; // 将第一个窗口的和设为最大和// 滑动窗口，从第k个数字开始for (int i = k; i < n; i++) {currentSum = currentSum - nums[i - k] + nums[i]; // 滑动窗口，更新当前窗口的和maxSum = Math.max(maxSum, currentSum); // 更新最大和}return maxSum; // 返回最大和}
}
七、效果展示
1、输入
5,-1,5,-2,8,3
3
2、输出
11
3、说明
- 初始窗口为 5,-1,5，和为 9。
- 移动窗口后，窗口为 -1,5,-2，和为 2。
- 后续窗口为 5,-2,8，和为 11，更新最大和。
- 最后窗口为 -2,8,3，和为 9，保持最大和为 11。
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
 - 滑动窗口（Java 2024 E卷 100分） "华为OD机试 - 阿里巴巴找黄金宝箱(V) - 滑动窗口（Java 2024 E卷 100分）")
