华为OD机试2025A卷-滑动窗口最大和[100分]（Java_Python3_C++_JsNode_Go）实现100%通过率

前言

华为OD机试2025A卷 是华为外包岗位招聘中机试环节的题目集合，其中"滑动窗口最大和"是一道经典的定长滑动窗口题目。本题考察的是窗口和的递推维护，即窗口每滑动一格时如何 O(1) 更新窗口和。题目分值100分，难度较低，是滑动窗口最基础的应用题。本文将提供5种语言的完整实现（C++、Java、Python3、JavaScript、Go），每种语言的代码都附带详细的中文注释，帮助读者彻底理解定长窗口滑动与窗口和递推的建模与求解过程。建议在阅读代码时，重点关注窗口未满时的扩张、窗口满后整体右移时"减左端、加右端"的递推逻辑。

一：题目描述

滑动窗口最大和

题目名称：滑动窗口最大和

【题目描述】

有一个 N 个整数的数组，和一个长度为 M 的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，每次窗口滑动产生一个窗口和（窗口内所有数的和），求窗口滑动产生的所有窗口和的最大值。

【输入格式】

• 第一行输入一个正整数 N，表示整数个数。（0 < N < 100000）
• 第二行输入 N 个整数，整数的取值范围为 [-100, 100]。
• 第三行输入一个正整数 M，M 代表窗口的大小，M <= 100000，且 M <= N。

【输出格式】

窗口滑动产生的所有窗口和的最大值。

【示例1】

输入：

6
10 20 30 15 23 12
3

输出：

68

解释：窗口大小为 3，依次得到窗口和 10+20+30=60、20+30+15=65、30+15+23=68、15+23+12=50，最大值为 68。

【示例2】

输入：

5
1 2 3 4 5
2

输出：

9

解释：窗口大小为 2，窗口和依次为 3、5、7、9，最大值为 9。

二：解题思路

解法一：每个窗口重新求和（不推荐）

暴力做法是对每个窗口位置都把窗口内的 M 个数重新累加一遍。共有 O(N) 个窗口，每个窗口求和 O(M)，总时间复杂度 O(N × M)。当 N、M 都达到 10 万时，计算量高达百亿次，完全无法在规定时间内通过，因此必须递推维护窗口和。

解法二：定长窗口滑动 + 窗口和递推（最优解）

核心建模

窗口大小固定为 M。用 left、right 两个指针表示窗口边界，用 tmp 记录当前窗口内数字之和。窗口每向右滑动一格，其实只是移出最左边一个数、加入最右边一个新数，因此窗口和可以 O(1) 递推：

• 窗口和 = 旧窗口和 − 移出的左端元素 + 新加入的右端元素。

这样全程只需遍历数组一次。

窗口的扩张与滑动

初始最大值要足够小

数组元素可能为负数，窗口和也可能为负，因此记录最大值的 res 要初始化为一个很小的数（如负无穷），不能初始化为 0，否则全负数据会错误地输出 0。

实际步骤总结：

三：代码实现

C++

#include<iostream>
#include<vector>
#include<string>
#include <utility>
#include <sstream>
#include<algorithm>
#include<list>
#include<queue>
#include<map>
#include<set>
using namespace std;

int main() {
int n, m;
cin >> n;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
cin >> ans[i];
}
cin >> m;
// left 左边界 right右边界下一个选择的位置
int left = 0, right = 0;
int res = –100000000;
int tmp = 0;

while (right < n) {
// 只考虑窗口为M的情况
if (right – left + 1 < m) {
tmp += ans[right];
right++;
continue;
}
// 窗口大小为M+1，left 右移
if (right – left + 1 > m) {
tmp -= ans[left];
left++;
}
tmp += ans[right];
res = max(res, tmp);
right++;
}

cout << res;
return 0;
}

Java

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 输入数组长度
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = sc.nextInt();
}

int m = sc.nextInt(); // 滑动窗口大小

int left = 0, right = 0;
int res = Integer.MIN_VALUE;
int tmp = 0;

while (right < n) {
// 窗口还不够大，继续加元素
if (right – left + 1 < m) {
tmp += ans[right];
right++;
continue;
}

// 窗口太大了，缩小窗口
if (right – left + 1 > m) {
tmp -= ans[left];
left++;
}

tmp += ans[right];
res = Math.max(res, tmp);
right++;
}

System.out.println(res);
}
}

Python3

# -*- coding: utf-8 -*-
n = int(input())
ans = list(map(int, input().split()))
m = int(input())

left = 0
right = 0
res = –10**9
tmp = 0

while right < n:
# 窗口还没满，继续加
if right – left + 1 < m:
tmp += ans[right]
right += 1
continue

# 窗口太大了，缩小
if right – left + 1 > m:
tmp -= ans[left]
left += 1

tmp += ans[right]
res = max(res, tmp)
right += 1

print(res)

JavaScript

const readline = require("readline");

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let inputLines = [];

rl.on("line", function (line) {
inputLines.push(line.trim());
if (inputLines.length === 3) {
main();
rl.close();
}
});

function main() {
const n = parseInt(inputLines[0]);
const ans = inputLines[1].split(' ').map(Number);
const m = parseInt(inputLines[2]);

let left = 0, right = 0;
let res = –1e9;
let tmp = 0;

while (right < n) {
// 窗口不够大
if (right – left + 1 < m) {
tmp += ans[right];
right++;
continue;
}

// 窗口太大
if (right – left + 1 > m) {
tmp -= ans[left];
left++;
}

tmp += ans[right];
res = Math.max(res, tmp);
right++;
}

console.log(res);
}

Go

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

func main() {
reader := bufio.NewReader(os.Stdin)

// 读取 n
line, _ := reader.ReadString('\\n')
n, _ := strconv.Atoi(strings.TrimSpace(line))

// 读取数组
line, _ = reader.ReadString('\\n')
fields := strings.Fields(line)
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i], _ = strconv.Atoi(fields[i])
}

// 读取 m
line, _ = reader.ReadString('\\n')
m, _ := strconv.Atoi(strings.TrimSpace(line))

left, right := 0, 0
res := –100000000
tmp := 0

for right < n {
if right–left+1 < m {
tmp += ans[right]
right++
continue
}

if right–left+1 > m {
tmp -= ans[left]
left++
}

tmp += ans[right]
if tmp > res {
res = tmp
}
right++
}

fmt.Println(res)
}

四：复杂度分析

五：易错点