华为OD机试 - 阿里巴巴找黄金宝箱(V) - 滑动窗口（Python/JS/C/C++ 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/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 开始，逐步向右移动窗口，每次移动时，去掉窗口最左边的元素，加入窗口最右边的元素。这样，我们就可以通过简单的加减操作更新窗口的和，而不需要重复计算整个窗口。
- 记录最大和：在每次滑动窗口时，比较当前窗口的和和最大和，保留较大者。
- 返回结果：最后输出最大和。
六、Python算法源码
# 定义主函数
def main():
# 读取输入的数字字符串并将其分割为整数数组
num_str = input().split(',')
nums = list(map(int, num_str)) # 将字符串列表转换为整数列表
# 读取咒语数字 k
k = int(input())
# 调用计算最大连续 k 个数的和的函数
print(max_sum(nums, k))
# 计算最大连续 k 个宝箱数字和
def max_sum(nums, k):
n = len(nums) # 获取数组长度
# 初始化第一个窗口的和
current_sum = sum(nums[:k]) # 计算前 k 个数字的和
max_sum = current_sum # 将第一个窗口的和设为最大和
# 滑动窗口，从第 k 个数字开始
for i in range(k, n):
current_sum = current_sum - nums[i - k] + nums[i] # 滑动窗口，更新当前窗口的和
max_sum = max(max_sum, current_sum) # 更新最大和
return max_sum # 返回最大和
# 运行主程序
if __name__ == "__main__":
main()
七、JavaScript算法源码
// 定义主函数
function main() {
// 读取输入的数字字符串并分割成整数数组
const numStr = prompt("Enter numbers:").split(',');
const nums = numStr.map(Number); // 将字符串数组转换为整数数组
// 读取咒语数字 k
const k = parseInt(prompt("Enter k:"));
// 调用计算最大连续 k 个数的和的函数
console.log(maxSum(nums, k));
}
// 计算最大连续 k 个宝箱数字和
function maxSum(nums, k) {
const n = nums.length; // 获取数组长度
// 初始化第一个窗口的和
let currentSum = 0;
for (let i = 0; i < k; i++) {
currentSum += nums[i]; // 计算第一个窗口的和
}
let maxSum = currentSum; // 将第一个窗口的和设为最大和
// 滑动窗口，从第 k 个数字开始
for (let i = k; i < n; i++) {
currentSum = currentSum - nums[i - k] + nums[i]; // 滑动窗口，更新当前窗口的和
maxSum = Math.max(maxSum, currentSum); // 更新最大和
}
return maxSum; // 返回最大和
}
// 运行主程序
main();
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 函数声明
int maxSum(int* nums, int k, int n);
int main() {
char input[1000000]; // 用于存储输入字符串
fgets(input, sizeof(input), stdin); // 读取输入的数字字符串
// 分割输入字符串并转换为整数数组
char* token = strtok(input, ",");
int nums[100000]; // 假设最多有100000个数字
int count = 0;
while (token != NULL) {
nums[count++] = atoi(token); // 将字符串转为整数并存入数组
token = strtok(NULL, ",");
}
int k;
scanf("%d", &k); // 读取咒语数字 k
// 调用计算最大连续 k 个数的和的函数并打印结果
printf("%d\n", maxSum(nums, k, count));
return 0;
}
// 计算最大连续 k 个宝箱数字和
int maxSum(int* nums, int k, int n) {
// 初始化第一个窗口的和
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]; // 滑动窗口，更新当前窗口的和
if (currentSum > maxSum) {
maxSum = currentSum; // 更新最大和
}
}
return maxSum; // 返回最大和
}
九、C++算法源码
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
// 函数声明
int maxSum(vector<int>& nums, int k);
int main() {
string input;
getline(cin, input); // 读取输入的数字字符串
// 分割输入字符串并转换为整数数组
vector<int> nums;
stringstream ss(input);
string temp;
while (getline(ss, temp, ',')) {
nums.push_back(stoi(temp)); // 将每个字符串转换为整数并存入数组
}
int k;
cin >> k; // 读取咒语数字 k
// 调用计算最大连续 k 个数的和的函数并打印结果
cout << maxSum(nums, k) << endl;
return 0;
}
// 计算最大连续 k 个宝箱数字和
int maxSum(vector<int>& nums, int k) {
int n = nums.size(); // 获取数组长度
// 初始化第一个窗口的和
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 = max(maxSum, currentSum); // 更新最大和
}
return maxSum; // 返回最大和
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
