华为OD机考C卷真题：最佳升级时间窗与滑动窗口算法全解

最近不少人私信我都在问华为OD机考到底怎么准备。翻来覆去聊得最多的就是这道“最佳升级时间窗”。这题在C卷里出现频率相当高而且要求你用Java、Python、JS、GO、C、C这六种语言都能写出正确答案。我干脆把这题的完整思路、六语言实现、机考实战经验一次讲透不管你是正在刷华为OD机考C卷真题还是单纯想练滑动窗口算法这篇文章都值得你花10分钟读完。先说结论这道题考的不是高深算法而是基本功——双指针滑动窗口。但越基础的题越容易在细节上翻车比如sum用int存导致溢出、while写成if、输出日期忘记加1这些我都见过。下面按我的实战流程一步步拆解。1. 题目到底在考什么背景、题面与核心算法1.1 华为OD机考是什么双机位C卷意味着什么华为OD机考是软件研发岗位候选人要过的第一关通常采用在线OJ平台完成上机考试。所谓“双机位C卷”指的是考试用两个摄像头监控一个对准正面另一个放在侧后方或桌面侧方用来防作弊C卷是题库卷的代号不同批次会抽到不同卷子但题目都是从题库里出的。“最佳升级时间窗”就是C卷里一道典型的区间求和题归在双指针/滑动窗口这个大类下。我刷了这些年算法题对OD机考的整体感受是难度介于LeetCode简单题和中等题之间很少出压轴级别的难题但非常喜欢在边界条件上做文章。比如数组长度直接给到10^5target给到10^9你要是老老实实用int存总和前面逻辑全对也照样WA。所以准备这类考试重点不是背题而是把“读题→识别算法→处理边界→输出格式”这整条链路练到肌肉记忆。1.2 完整题面与样例解析我按自己在机考里遇到的版本整理一下题面小华在玩一款手游游戏开服后连续开放N天第i天登录可以获得a[i]点活跃值a[i]为正整数。现在有一个“升级冲刺”活动玩家可以任选一个连续的时间段进行冲刺要求该时间段内获得的活跃值总和至少达到target且时间段天数尽可能短。如果有多个天数相同的最短时间段输出开始日期最早的。请找出这个“最佳升级时间窗”输出窗口的起始日与结束日1-based。如果不存在满足条件的窗口输出 0 0。输入格式 第一行两个整数 N target 第二行 N 个整数 a1 a2 ... aN输出格式 一行两个整数 start end1-based或 0 0。样例输入 6 8 4 2 3 1 5 1样例输出 1 3样例解释连续一天最大是5达不到8连续两天里426、235、314、156、516也都达不到8连续三天里第1到第3天相加4239满足条件第3到第5天相加3159也满足但题目要求取开始日期最早的所以答案是1 3。这个样例设计得很典型它同时考察了“最短长度”和“相同长度取最早”两个规则。你要是只看长度不看起始日很容易输出3 5那就踩坑了。1.3 为什么是滑动窗口而不是暴力最直白的做法是枚举所有连续子数组求和复杂度O(N^2)。当N10^5时要算10^10次加法在线OJ上是不可能过的。滑动窗口能把总操作数降到2N每个元素最多被加入sum一次、被移除sum一次整体是线性复杂度。这题能滑动的前提是a[i]都是正整数窗口和随着窗口扩大只增不减。有了这个单调性我们就可以用两个指针维护一个窗口右指针往右走扩大窗口把新元素加进sum一旦sum target就尝试用左指针往右收缩看看能不能用更短的窗口满足条件收缩到sum target为止再继续扩大右指针。这个过程很像收银台满减右指针是不断扫码入篮的新商品左指针是最早放进篮子的商品。总价刚够满减时先把最早的商品放回去几件看看当前手里最短的组合是什么然后继续扫后面的商品。为什么不会漏解把所有可行窗口按右端点分类。对每一个右端点双指针扫描过程中会把“以它作为右端点、并且是最短”的那个可行窗口都找出来。全局最优解必然属于某一个右端点类别所以被覆盖到了。这个论证想明白了滑动窗口就算真正理解了。2. 双指针算法推导思路、边界与复杂度2.1 双指针移动规则详解整个算法的状态量很少就四个left、right、sum、答案。具体流程left初始为0sum初始为0right从0遍历到N-1每次执行sum a[right]只要left right且sum target记录当前窗口长度是right - left 1然后sum - a[left]left继续收缩收缩到sum target或者left right跳出whileright继续扩展。这里最关键的一点是内部收缩必须用while而不是if。我第一次写这题时图省事用了if结果窗口只缩了一步就停了后面很多满足条件的短窗口根本没被枚举到样例过了数据一大就错。你要记住收缩的目的是把当前窗口缩到“刚好不满条件”的状态这可能需要连续减掉多个左边元素。拿前面的样例手动推演一遍 a [4, 2, 3, 1, 5, 1]target 8。right0sum4小于8继续right1sum6小于8继续right2sum9满足记录左0右2长度3sum减去a[0]4left变为1sum5跳出right3sum6小于8继续right4sum11满足left1记录左1右4长度4sum减a[1]2变为9left2仍满足记录左2右4长度3sum减a[2]3变为6left3跳出right5sum7小于8结束。候选窗口有左0右2和左2右4长度都是3取开始日期更早的左0右2输出1 3。整个过程可以看到right每走一步while都会把以当前right为右端点的可行窗口扫干净保证不漏解。2.2 最容易踩的3个边界细节边界1找不到合法窗口时的输出。不同版本题面要求不一样有的输出0 0有的输出-1 -1。看清楚再写别想当然。本文样例是输出0 0。边界2答案初始值别用-1。我推荐用一个“不可能”的兜底值比如best n 1。最后判断best是否还是n 1如果是就输出兜底结果。有人喜欢用Integer.MAX_VALUE也可以但要注意别在比较时把MAX_VALUE和某个窗口长度相加导致溢出这题不会但养成习惯没坏处。边界3输出是1-based下标。数组下标从0开始但题目要求输出的是第几天到第几天所以是left1和right1。忘加1是这题最常见的低级错误尤其是样例恰好是某个对称窗口时很容易看不出来。还有一个容易忽视的点相等长度取最早。我代码里更新条件是len best或者len best但left更早。其实由于右指针是从左往右扫的相同长度的窗口一定是左边的先被扫描到所以只写len best通常也对。但为了语义清晰我建议还是显式写清楚相等时的规则防止题面要求“取最晚”这种变体时反应不过来。2.3 复杂度分析与优化思路时间复杂度O(N)right走N步left最多也走N步总操作次数约2N。空间复杂度O(1)只有几个整型变量和结果变量不需要额外数组。这个复杂度已经是该类问题的最优解。如果不用双指针另一种做法是前缀和二分先预处理前缀和数组pre然后枚举每个左端点在pre里二分查找第一个使pre[j] - pre[i] target的j时间复杂度O(N log N)空间O(N)。能过但不如O(N)的双指针优雅。有的大厂面试官会追一句“能用O(N)做吗”所以双指针才是这题的理想答案。3. 六种语言实现ACM模式下的完整代码与踩坑记录3.1 Java实现读入输出与long类型Java代码我用的是Scanner模式写起来直观import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNext()) { int n sc.nextInt(); long target sc.nextLong(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int left 0; long sum 0; int bestLen n 1; int ansStart -1; int ansEnd -1; for (int right 0; right n; right) { sum a[right]; while (left right sum target) { int len right - left 1; if (len bestLen || (len bestLen left 1 ansStart)) { bestLen len; ansStart left 1; ansEnd right 1; } sum - a[left]; left; } } if (bestLen n 1) { System.out.println(0 0); } else { System.out.println(ansStart ansEnd); } } } }几个注意点sum和target一定要用long。a[i]如果到10^9N到10^5sum能到10^14int直接炸。我用while(sc.hasNext())包裹兼容多组测试用例如果题目明确只有一组去掉这层while也行。如果输入规模特别大Scanner换成BufferedReader StringTokenizer性能更好但OD机考的数据量用Scanner基本够。3.2 Python实现最推荐给初学者的版本Python代码非常简洁适合追求效率的选手import sys def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) target int(next(it)) a [int(next(it)) for _ in range(n)] left 0 total 0 best_len n 1 ans_start -1 ans_end -1 for right in range(n): total a[right] while left right and total target: length right - left 1 if length best_len or (length best_len and left 1 ans_start): best_len length ans_start left 1 ans_end right 1 total - a[left] left 1 if best_len n 1: print(0 0) else: print(ans_start, ans_end) if __name__ __main__: solve()为什么推荐sys.stdin.read().split()而不是input()因为当N到10^5时for循环里调用input()会产生大量IO开销而一次性读取再split要快得多。另外Python的int没有长度上限彻底不用考虑溢出问题这点对新手特别友好。3.3 JS / GO / C / C 实现要点JS在牛客这类平台的写法是Node.js环境要用readline异步读入const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) lines.push(line.trim())); rl.on(close, () { const nums lines.join( ).split(/\s/).map(Number); let idx 0; const n nums[idx]; const target nums[idx]; const a nums.slice(idx, idx n); let left 0; let sum 0; let bestLen n 1; let ansStart -1; let ansEnd -1; for (let right 0; right n; right) { sum a[right]; while (left right sum target) { const len right - left 1; if (len bestLen || (len bestLen left 1 ansStart)) { bestLen len; ansStart left 1; ansEnd right 1; } sum - a[left]; left; } } if (bestLen n 1) { console.log(0 0); } else { console.log(ansStart ansEnd); } });JS最大的坑是readline的异步处理很多人一开始直接在on(line)里算答案结果前几行数据还没读完就输出了。正确做法是把所有行收集起来在close回调里统一解析。另外数字精度用Number够用题目给的区间和一般在10^14量级没超过Number安全整数范围。GO实现package main import fmt func main() { var n int var target int64 fmt.Scan(n, target) a : make([]int, n) for i : range a { fmt.Scan(a[i]) } left : 0 var sum int64 bestLen : n 1 ansStart, ansEnd : -1, -1 for right : 0; right n; right { sum int64(a[right]) for left right sum target { length : right - left 1 if length bestLen || (length bestLen left1 ansStart) { bestLen length ansStart left 1 ansEnd right 1 } sum - int64(a[left]) left } } if bestLen n1 { fmt.Println(0 0) } else { fmt.Println(ansStart, ansEnd) } }GO的fmt.Scan能按空白符自动分割写起来省事。这里我用int64存target和suma[i]读成int后再显式转int64避免在加法过程中溢出。C实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long target; cin n target; vectorlong long a(n); for (auto x : a) cin x; int left 0; long long sum 0; int bestLen n 1; int ansStart -1, ansEnd -1; for (int right 0; right n; right) { sum a[right]; while (left right sum target) { int len right - left 1; if (len bestLen || (len bestLen left 1 ansStart)) { bestLen len; ansStart left 1; ansEnd right 1; } sum - a[left]; left; } } if (bestLen n 1) cout 0 0\n; else cout ansStart ansEnd \n; return 0; }C选手最常犯的错还是类型int n读到10^5没问题但sum和target必须long long。另外开头两行关流同步能显著加快读入在输入大的时候能省接近一半时间。C语言实现#include stdio.h int main() { int n; long long target; scanf(%d %lld, n, target); long long a[n]; for (int i 0; i n; i) scanf(%lld, a[i]); int left 0; long long sum 0; int bestLen n 1; int ansStart -1, ansEnd -1; for (int right 0; right n; right) { sum a[right]; while (left right sum target) { int len right - left 1; if (len bestLen || (len bestLen left 1 ansStart)) { bestLen len; ansStart left 1; ansEnd right 1; } sum - a[left]; left; } } if (bestLen n 1) printf(0 0\n); else printf(%d %d\n, ansStart, ansEnd); return 0; }C语言版本的a[n]用C99变长数组如果平台不支持改成malloc动态分配。scanf读long long要用%lld别忘了。数组越界是C语言特有的隐患好在滑动窗口的while条件里已经写了left right只要不手滑问题不大。3.4 六语言对比表你在机考里该选哪门语言代码风格复杂度最大坑点适合人群Java偏长、类结构清晰O(N)/O(1)sum溢出、Scanner偏慢企业后端岗位求职者Python最简洁O(N)/O(1)输入读取方式写代码追求效率的选手JS回调式读入O(N)/O(1)readline异步、数字精度前端转岗候选人GO静态但简单O(N)/O(1)int64转换云原生/后端方向C高性能O(N)/O(1)long long遗忘ACM习惯选手C原始但快O(N)/O(1)数组越界、%lld对性能有执念的选手表格里列的是“使用该语言最容易踩的坑”但机考的核心原则只有一条用你最熟的语言而不是看起来最酷的语言。Java熟练的人硬写C结果被指针搞得心态崩了完全没必要。4. 机考实战从拿到题到AC的完整套路4.1 拿到题之后的5步拆解流程我在考场上拿到一道题一般只做5步看数据范围。看到N是10^5到10^6立刻排除O(N^2)暴力。看是否“连续区间”。题目出现“连续子数组”“连续时间段”“至少/至多”信号指向滑动窗口或前缀和。确认单调性。题面说a[i]是正整数区间和随长度单调递增滑动窗口可行。确定答案更新规则。这题要求最短最早那就在收缩阶段更新答案并显式比较长度和起始下标。编码前先想清楚输出形式。输出0 0还是-1 -11-based还是0-based这些在动手指前必须明确。这套流程熟练后一道中等题从读题到写完代码基本8分钟能搞定。剩下时间全用来自测边界。4.2 机考输入输出的几个坑输入输出是机考里最大的“非算法陷阱”。常见的坑有这些输入可能有行尾空格、多余空行、换行分割的数字。用题目给的读取方式最稳Java的Scanner、Python的split都能自动处理空白符。输出不能有多余内容。调试时用的System.err、console.log在提交前要删干净否则OJ把这些也当成输出的一部分直接判错。核心代码模式和ACM模式不一样。有的平台只需要你实现一个函数有的要求自己处理全部IO。别把两种模式搞混否则要么编译不过要么死循环等输入。多组测试用例的情况要看题目描述。有的题明确说“输入可能包含多组”这时候要包一层while读入有的只说一组写成死循环读入反而会超时。另外说一点环境有关的双机位考场基本都会提前要求清空桌面、检查摄像头角度。与其到时候被监考提醒打断思路不如提前把桌面收拾干净。考试期间也不要动切屏看资料的念头双机位监控会记录异常操作真被判了作弊整个成绩作废得不偿失。4.3 自测与调试如何保证一次过写完代码别急着交用下面几个用例快速自测全数组之和都小于target。比如“3 10 / 1 2 3”应输出0 0。第一个元素就满足条件。比如“5 99 / 100 1 1 1 1”应输出1 1。两个窗口长度一样但起始不同。比如样例“6 8 / 4 2 3 1 5 1”应输出1 3而不是3 5。边界N1且a[0] target输出1 1。大数据验证N100000数组全1target50000预期输出“1 50000”。这个用例能顺便测出sum有没有用错类型。这些用例构造起来不到两分钟但能覆盖掉大部分低级错误。我见过太多人样例一过就交结果栽在“长度相同取最早”这个点上冤得很。4.4 常见问题速查表现象可能原因解决办法不断超时用了O(N^2)暴力枚举改成双指针滑动窗口大数据下答案全错sum用了int溢出换成long/long long/int64输出日期比预期大1忘记1-based转换输出left1、right1窗口没有缩到最短收缩用了if而不是while改成while循环明明满足条件却找不到答案target或sum类型读错检查读取顺序和类型长度相同但选错窗口更新条件没有处理相等情况显式比较left下标5. 一题多得从“最佳升级时间窗”延伸出的算法变体5.1 变体一恰好等于target的最短子数组如果题目从“至少达到target”改成“恰好等于target”双指针还是首选吗我的建议是不要直接套换前缀和哈希更踏实。思路设pre[j]表示前j个元素的和pre[0]0。要找一个区间[i, j)使得pre[j] - pre[i] target等价于pre[i] pre[j] - target。遍历j时用哈希表记录每个pre[i]出现过的最靠右位置然后查pre[j] - target是否存在。这样能在O(N)时间内找出所有满足条件的区间再取最短和最早。核心片段大概长这样pos {0: -1} best n 1 ans (-1, -1) cur 0 for j in range(n): cur a[j] need cur - target if need in pos: i pos[need] 1 if j - i 1 best: best j - i 1 ans (i 1, j 1) pos[cur] j这里哈希表存的是每个前缀和值最后一次出现的位置这样查出来的区间是“最近的”有助于找最短。这个变体是C卷里另一种高频考法建议和原题一起刷。5.2 变体二固定窗口长度的滑动窗口最值另一类高频滑动窗口题是固定窗口大小k求每个窗口内的最大值或最小值。这题和“最佳升级时间窗”都叫滑动窗口但解法完全不同要用单调队列。维护一个双端队列队头是当前窗口的最大值下标。新元素入队时从队尾弹出所有比它小的元素窗口滑动时从队头弹出下标已经不在窗口范围内的元素。这样每个元素最多入队出队一次整体O(N)。它和双指针滑动窗口的区别在于双指针是靠窗口和做约束单调队列是靠窗口内元素的“淘汰规则”做优化。5.3 变体三二维矩阵的最小子矩阵和把一维问题扩展到二维给一个m×n矩阵找一个面积最小的子矩形使矩形内元素之和target。做法是枚举矩形的上边界r1和下边界r2然后把每一列在r1到r2之间的元素纵向累加成一个一维数组对这个一维数组做双指针。每列纵向和是非负的所以转化出来的一维数组仍满足单调性。枚举上下边界的复杂度O(M^2)内部双指针O(N)总复杂度O(M^2·N)。M和N都在300以内时完全可行。这类二维压缩成一维的技巧在矩阵相关的区间题里经常出现从这题延伸出去理解会很顺畅。我个人刷这道题的真实感受是滑动窗口的套路就是三板斧——右指针进、左指针出、while里更新答案。第一次写容易把while写成if第二次会忘记long第三次才能做到一次过。所以别嫌题目简单能在考场稳定复现才说明真正把它掌握了。要是你也在准备华为OD机考C卷建议把这题用自己最熟的语言刷三遍再把我说的几个边界用例跑一遍基本就能放心上考场了。