一、真题

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

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

输出描述
窗口滑动产生所有窗口和的最大值。

示例 1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
6
12 10 20 30 15 23
3
输出
68

二、题目分析与解题思路🧠

1. 题目重述

• 输入：
  1. 整数 N （数组长度）。
  2. N 个整数（数组元素，范围 [-100, 100]）。
  3. 整数 M （窗口大小， M≤N ）。
• 过程：一个长度为 MM 的窗口在数组上从左向右滑动，每次移动一步。
• 目标：计算所有滑动位置中，窗口内元素之和的 最大值。

2. 核心痛点：为什么暴力法会超时？

• 暴力思路：对于每个起始位置 i ，循环 M 次累加求和。
• 复杂度： O(N×M) 。
• 数据爆炸：当 N=10^5，M=5×10^4 时，运算次数高达 5×10^9 。
  • Python/JS 等解释型语言每秒通常只能处理 10^7 量级的操作。
  • 结果：运行时间超过 10 秒，直接 Time Limit Exceeded (TLE)。

3. 破局之道：滑动窗口 (Sliding Window)

• 观察：
  • 窗口 i 的和 = A[i]+A[i+1]+...+A[i+M−1]
  • 窗口 i+1 的和 = A[i+1]+...+A[i+M−1]+A[i+M]
  • 关系：Sum(i+1) = Sum(i) - A[i] + A[i+M]
• 策略：
  1. 先计算第一个窗口（索引 0 到 M−1 ）的和。
  2. 从索引 M 开始遍历，每次只需 减去 最左边滑出的元素，加上 最右边滑入的元素。
  3. 实时更新最大值。
• 复杂度： O(N) 。只需遍历一次数组，运算量约 10^5 次，毫秒级完成。

---

三、Python 3 实现 (简洁高效版)

Python 以其语法简洁著称，但在处理大量输入时，需要注意输入读取的效率。本题数据量较大，建议使用 sys.stdin。

python

编辑

import sys

def solve():
    # 读取所有输入行，处理可能的空行或格式问题
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        # 1. 读取 N
        n = int(next(iterator))
        
        # 2. 读取 N 个整数
        nums = []
        for _ in range(n):
            nums.append(int(next(iterator)))
            
        # 3. 读取 M
        m = int(next(iterator))
    except StopIteration:
        return

    # 边界条件检查
    if m > n or m <= 0:
        # 根据题意 M<=N，但防御性编程是好习惯
        print(0)
        return

    # --- 核心算法：滑动窗口 ---
    
    # 1. 计算第一个窗口的和 (索引 0 到 m-1)
    current_sum = sum(nums[:m])
    max_sum = current_sum
    
    # 2. 滑动窗口：从索引 m 开始遍历到 n-1
    # i 代表当前新加入窗口的元素的索引
    # i-m 代表当前要移出窗口的元素的索引
    for i in range(m, n):
        # 状态转移方程：新和 = 旧和 - 移出元素 + 移入元素
        current_sum = current_sum - nums[i - m] + nums[i]
        
        # 更新最大值
        if current_sum > max_sum:
            max_sum = current_sum
            
    print(max_sum)

if __name__ == "__main__":
    solve()

✅ Python 版亮点

• sys.stdin.read().split()：一次性读取所有输入并按空白符分割，避免了多次 input() 调用的开销，也能自动处理数字间的多个空格或换行符，非常稳健。
• 切片初始化：sum(nums[:m]) 利用 Python 底层优化的 C 代码快速计算初始和。
• 逻辑清晰：循环中仅做加减法和比较，完全符合 O(N) 要求。

---

四、JavaScript 实现 (异步 IO 版)

在 Node.js 环境中，处理标准输入需要使用 readline 模块或监听 process.stdin。为了应对大数据量，我们采用流式读取并缓冲数据。

const readline = require('readline');

// 创建 readline 接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
let lineCount = 0;

// 监听每一行输入
rl.on('line', (line) => {
    // 去除首尾空格，如果行为空则跳过（防止空行干扰）
    const trimmed = line.trim();
    if (trimmed) {
        lines.push(trimmed);
    }
});

// 输入结束处理
rl.on('close', () => {
    if (lines.length === 0) return;

    // 解析输入
    // 注意：输入可能分散在多行，也可能在一行，我们需要将所有数字提取出来
    // 这里假设输入格式严格遵循题目描述：
    // Line 1: N
    // Line 2: N个整数 (可能很长，或者被拆分，但题目描述是一行)
    // Line 3: M
    
    // 为了鲁棒性，我们将所有行合并后用空格分割成一个大的 token 数组
    const allTokens = lines.join(' ').split(/\s+/);
    let idx = 0;

    if (idx >= allTokens.length) return;
    const n = parseInt(allTokens[idx++], 10);

    const nums = new Array(n);
    for (let i = 0; i < n; i++) {
        if (idx >= allTokens.length) break;
        nums[i] = parseInt(allTokens[idx++], 10);
    }

    if (idx >= allTokens.length) return;
    const m = parseInt(allTokens[idx++], 10);

    // 边界检查
    if (m > n || m <= 0) {
        console.log(0);
        return;
    }

    // --- 核心算法：滑动窗口 ---

    // 1. 计算第一个窗口的和
    let currentSum = 0;
    for (let i = 0; i < m; i++) {
        currentSum += nums[i];
    }

    let maxSum = currentSum;

    // 2. 滑动窗口
    // i 从 m 开始，代表新进入窗口的元素索引
    for (let i = m; i < n; i++) {
        // 减去滑出的元素 (i-m)，加上滑入的元素 (i)
        currentSum = currentSum - nums[i - m] + nums[i];
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }

    console.log(maxSum);
});

✅ JavaScript 版亮点

• 鲁棒的输入解析：使用 lines.join(' ').split(/\s+/) 将所有输入合并后按空白符分割。这能有效应对数字分布在多行、或一行中有多个连续空格的各种奇怪测试用例。
• 线性扫描：逻辑与 Python 版一致，确保 O(N) 效率。
• 变量类型：JS 的 Number 类型足以处理本题范围内的整数和（最大约 10^7 ），无需担心溢出。

---

五、算法图解与逻辑推演

假设输入：
N=6, nums=[12, 10, 20, 30, 15, 23], M=3

1. 初始窗口 [12, 10, 20] (索引 0~2)

   • currentSum = 12 + 10 + 20 = 42
   • maxSum = 42

2. 第一次滑动 (i=3, 元素 30)

   • 移出 nums[3-3] = nums[0] = 12
   • 移入 nums[3] = 30
   • currentSum = 42 - 12 + 30 = 60
   • maxSum = max(42, 60) = 60
   • 窗口内容：[10, 20, 30]

3. 第二次滑动 (i=4, 元素 15)

   • 移出 nums[1] = 10
   • 移入 nums[4] = 15
   • currentSum = 60 - 10 + 15 = 65
   • maxSum = 65
   • 窗口内容：[20, 30, 15]

4. 第三次滑动 (i=5, 元素 23)

   • 移出 nums[2] = 20
   • 移入 nums[5] = 23
   • currentSum = 65 - 20 + 23 = 68
   • maxSum = 68
   • 窗口内容：[30, 15, 23]

5. 结束，输出 68。

---

六、避坑指南⚠️

1. 初始化陷阱：
   • maxSum 必须初始化为 第一个窗口的和，而不能是 0 或负无穷。
   • 原因：如果数组全是负数（如 [-10, -20, -5]，M=2），最大和应该是 -15。如果初始化为 0，结果就会错误地变成 0。
2. 输入解析陷阱：
   • 题目说“第二行输入 N 个整数”，但在实际机考系统中，如果 N 很大，这行可能会非常长，或者被测试用例意外拆分成多行。
   • 对策：Python 的 read().split() 和 JS 的 join(' ').split() 都是无视换行符的通用解法，最安全。
3. 边界情况 M=NM=N ：
   • 此时循环 range(m, n) 不会执行，直接输出初始和，逻辑正确。
4. 负数范围：
   • 题目元素范围 [-100, 100]，即使 N=100,000 ，总和也在 int 范围内，无需特殊的大数处理。

---

七、性能对比总结📊

语言	推荐输入方式	时间复杂度	空间复杂度	适用场景
Python	sys.stdin.read()	O(N)	O(N)	快速开发，代码简短，逻辑清晰
JavaScript	readline + Buffer	O(N)	O(N)	前端全栈，Node.js 环境，事件驱动

两种语言在采用滑动窗口优化后，均能轻松在 50ms 内通过 10 万数据量的测试。

---

八、结语

滑动窗口是算法面试中的 基石技巧。

• 核心口诀：“定初值，滑一步，减旧加新，更最值”。
• 应用场景：不仅限于求和，还广泛用于求“最长无重复子串”、“最小覆盖子串”、“固定长度最大平均值”等问题。

掌握 Python 和 JS 的这两种实现，不仅能搞定华为 OD 的这道题，更能为你打开算法优化思维的大门。

觉得有帮助请 点赞👍、收藏⭐、关注🙋！下一期我们将挑战 双指针进阶：三数之和 (3Sum) 的 Python/JS 去重技巧