华为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 个数字的最大和。直接采用暴力算法虽然可以解决问题，但其时间复杂度较高，尤其是在数组较大时，效率会非常低下。

滑动窗口技术特别适合以下几种场景：

1. 连续子数组或子序列问题：滑动窗口通常用来解决连续的子数组或子序列的问题，比如本题中要求连续的 k 个数字的和。
2. 窗口大小固定：滑动窗口适用于固定窗口大小的场景，比如本题中，我们始终需要比较连续 k 个数字的和。

如果采用暴力解法，我们可以尝试遍历数组中每一个可能的长度为 k 的子数组，然后计算其和并与当前最大和进行比较。这种方法的复杂度是 O(N * k)，其中 N 是数组的长度。对于每一个可能的起点，我们都需要重新计算一遍 k 个数字的和，这样在处理大量数据时会非常耗时。

2、滑动窗口如何提升效率？

滑动窗口通过复用前一次的计算结果，减少了重复计算。具体来说，滑动窗口的做法是：

1. 计算第一个窗口的和。
2. 之后的每一个窗口，都可以通过从当前窗口的和中减去左边的元素，并加上右边的新元素来更新，而不需要重新计算整个窗口的和。

滑动窗口算法只需要遍历数组一次，时间复杂度是 O(N)，这显著提高了效率。

3、具体步骤：

这个问题属于经典的“滑动窗口”问题。我们需要找到给定数组中连续 k 个数字的最大和，滑动窗口算法非常适合这种问题。

解题思路如下：

1. 初始化窗口：首先计算前 k 个数字的和，作为初始窗口的和。
2. 滑动窗口遍历数组：从 k 开始，逐步向右移动窗口，每次移动时，去掉窗口最左边的元素，加入窗口最右边的元素。这样，我们就可以通过简单的加减操作更新窗口的和，而不需要重复计算整个窗口。
3. 记录最大和：在每次滑动窗口时，比较当前窗口的和和最大和，保留较大者。
4. 返回结果：最后输出最大和。

六、Python算法源码

# 定义主函数
def main():# 读取输入的数字字符串并将其分割为整数数组num_str = input().split(',')nums = list(map(int, num_str))  # 将字符串列表转换为整数列表# 读取咒语数字 kk = 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);  // 将字符串数组转换为整数数组// 读取咒语数字 kconst 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在线答疑。