我到底是怎么安排DHU机试Day7的：滑动窗口、前缀和与那些掉过的坑

刷题这东西，最怕的不是题目难，而是前六天练得好好的，一到第七天突然不知道该练什么。我把DHU机试题备战当成一个完整的训练周期来排，Day7正好卡在从基础语法向算法思维过渡的关键节点上。这一天我安排的题目不算多，但每道都值得反复做：一道无重复字符的最长子串，一道和为K的连续子数组，外加一道滑动窗口最大值的变式。这三道题覆盖了哈希表、双指针、前缀和三个机试最高频的考察方向，而且它们之间有一条非常清晰的逻辑主线——怎么用“窗口”或“区间”的概念去减少不必要的重复计算。今天这篇文章就把我Day7的全部思路、代码和踩坑记录完整写下来，给也在准备机试的朋友一个可以直接照做的参考。

先交代一下背景。我备考的是DHU的计算机类机试，东华大学的机试整体风格偏重基础数据结构和经典算法，大部分题目要求自己处理输入输出，类似ACM模式，和华为OD机试的考察逻辑有相通之处：题量不算大，但每一道题都在考你能不能把算法和工程习惯结合起来。所以我在Day7之前已经完成了数组遍历、哈希表基础、二分查找、双指针入门、递归与简单动态规划的铺垫，Day7的任务很具体：把“区间类”问题彻底啃透，为后面更复杂的动态规划打地基。

1. 先聊清楚：Day7为什么要选这三道题

1.1 机试知识点安排的逻辑

很多人在机试备考时容易陷入一个误区——今天刷十道简单题，明天直接挑战困难题，结果简单题没有内化，困难题又把自己打击得不行。我前期把整体节奏拆成了“基础语法—数据结构—高频算法专题—综合模拟”四个阶段，Day7正好处在第一轮算法专题的中段。在这个时间点安排滑动窗口和前缀和，是因为它们的核心思想“用空间记录历史状态”和“用指针维护有效范围”，几乎贯穿了后面所有中等难度的机试题。比如滑动窗口会用在字符串匹配、数组区间最大值；前缀和的思路则能直接迁移到二维矩阵、树上路径统计等场景。

我给自己定的Day7目标是三个：第一，把滑动窗口的模板写熟，能做到手写不卡壳；第二，理解前缀和为什么能用哈希表优化到O(n)；第三，通过实际运行测试，把输入输出、边界条件这些机试特有坑过一次。这三件事如果完成，Day7就算真正达标，而不是简单“做了几道题”。

1.2 关于DHU机试和华为OD机试的差异，你得心里有数

准备DHU机试的时候，我发现很多同学喜欢直接拿大厂机试的题库来练，这没问题，但要想清楚差异在哪。东华大学这类高校机试更看重基础功力，题目来源往往是经典的教材习题改编，给的输入范围相对友好，不会出现特别离谱的边界条件，但很爱考察细节，比如字符串是否包含空格、数组下标是否从0开始、多组输入如何结束。而华为OD机试更贴近工程实际，数据量有时候会给得很大，对时间复杂度的要求更苛刻，题目描述也更长，需要你快速从文本里提取真正的输入输出格式。两者的共同点是都必须阅读题目给定的输入输出约定，不能像LeetCode那样只填函数体。

Day7刷的这三道题我在两种模式下都试过一遍。在我自己的笔记里，LeetCode模式写核心逻辑往往十分钟能搞定，但换成ACM模式读数据就很容易翻车。所以我建议备考DHU的朋友，不要只在网页编辑器里刷题，一定要把代码复制到本地IDE里跑一遍，用System.in或标准输入模拟真实环境。尤其是Day7这种涉及多行输入的题目，输入输出处理不当，算法写得再对也是零分。

1.3 Day7题目的难度阶梯设计

一道题能不能真正提升机试水平，关键看它有没有训练到你欠缺的环节。所以我Day7的题目难度不是平均分配的，而是呈阶梯式：无重复字符的最长子串是滑动窗口的入门题，用来唤醒双指针的敏感度；和为K的子数组明显提升了一个档次，属于“暴力容易想到、优化要动脑筋”的题型；滑动窗口最大值则是典型的单调队列应用题，机试考得少一点，但对思维扩展很有帮助。这样安排的好处是，一天之内你有“会做—能做—需要看题解”三个层次的体验，不至于全程舒适区，也不至于全程都在怀疑人生。

2. 核心算法拆解之一：无重复字符的最长子串到底怎么滑

2.1 题目回顾与朴素思路

题目描述很简单：给定一个字符串s，找出其中不含有重复字符的最长子串的长度。比如输入"abcabcbb"，答案应该是3，因为最长无重复子串是"abc"；输入"bbbbb"，答案应该是1；输入"pwwkew"，答案是3，这里要特别注意子串是连续的，"wke"是答案，而"kew"虽然也是3，但题目只让我们返回长度，所以两者结果一样，不过如果你输出子串本身就得看准哪一个。

第一反应肯定是暴力：枚举所有起点和终点，检查这一段是否有重复字符，有就跳过，没有就更新答案。这个做法的时间复杂度是O(n²)甚至O(n³)，虽然简单，但一旦字符串长度接近十万级别，机试评测系统一定会给你一个超时。我Day7的第一道题就是要告别这种思维。

2.2 滑动窗口的动态维护过程

滑动窗口的精髓说起来很简单：我们维护一个左指针left和一个右指针right，表示当前窗口的范围[left, right]，窗口内保证没有重复字符。右指针每次向右扩展一格，如果新加入的字符和窗口内已有字符重复了，就把左指针移动到重复字符上一次出现位置的右边，重新让窗口合法。

这里我一开始踩过一个理解上的坑，就是“left移动到哪”。不是无脑left++，而是要根据哈希表里记录的字符最近出现位置来决定。举个例子，s="abba"：

• right=0，字符'a'，窗口[0,0]。
• right=1，字符'b'，窗口[0,1]。
• right=2，字符'b'，发现b上一次出现在1，所以left要跳到2，窗口[2,2]。
• right=3，字符'a'，a上一次出现在0，但此时left已经是2了，如果直接把left跳到1，窗口就变成[1,3]，里面包含两个b，直接出错。

所以正确写法是left = Math.max(left, map.get(c) + 1)，取上次出现位置+1和当前left的较大值，这才是真正的“窗口左边界只能向右移动”，不会因为旧信息把边界回退。

2.3 哈希表记录的是什么时机

这道题里HashMap的value记录的是字符最近一次出现的下标。每次遇到一个字符，先判断它是否在map中且下标大于等于left，再决定要不要移动left。你可能会问，为什么不直接记录Set，而是在遇到重复时从左边循环删除？那样也可以，但每次删除还需要额外维护当前窗口的字符集合，复杂度虽然还是O(n)，但代码反而更绕。用HashMap一次到位，本质上是用空间换了一次性定位的能力。Day7学会这个“最近出现位置”的存储习惯之后，后面很多涉及状态回溯的题目都受益。

3. 核心算法拆解之二：和为K的子数组，暴力到前缀和

3.1 为什么暴力法不适合机试

第二道题是经典中的经典：给定一个整数数组nums和一个整数k，返回数组中和为k的连续子数组的个数。第一眼看到“连续子数组”和“和”，很多人会想到两层循环枚举左右边界，再累加求和判断。确实能过小数据，但考场上你一定要看一眼数据范围，如果n到了10的5次方，O(n²)必死无疑，而且这道题真正的难点不在能不能做出来，而在能不能从“区间和”联想到“前缀和之差”。

什么是前缀和？就是用一个数组pre[i]表示nums[0]到nums[i-1]的和。那么从下标j到下标i-1的子数组和就可以写成pre[i] - pre[j]。于是“和为k的子数组”就被转成了一个等式：pre[i] - pre[j] = k，等价于pre[j] = pre[i] - k。我们的任务就变成了：在遍历过程中，数一下之前出现过多少个前缀和刚好等于pre[i] - k。这个数量就是当前i位置能贡献的子数组个数。

3.2 哈希表优化：把查找从O(n)降到O(1)

如果用数组来记录每个前缀和的出现次数，那你还是需要遍历整个前缀数组来找目标值。但用HashMap就完全不一样了：每算出一个新的前缀和pre，就去map里查“pre - k”出现了多少次，查到多少次就累加多少，然后把当前pre的计数加一。这里有一个很关键也很容易漏的初始化：一定要先往map里放入(0, 1)，表示前缀和为0出现过一次。为什么？因为如果前缀和本身就是k，那么pre - k等于0，这个子数组就是从0开始的，如果不提前放0的计数，这一类情况会全被漏掉。我记得第一次做这道题时就是忘了初始化，白白丢了好几个测试点，后面专门把“前缀和映射初始化0”写成了机试备忘录里的头号注意项。

3.3 一个容易搞混的细节：先查询还是先更新

代码的顺序一定要是“先统计，再更新”，不能反过来。假设k=0，数组是[0]，如果你先把前缀和0放入map，再查pre-k=0，那结果就是1，好像没问题。但假设数组是[1,-1]：

• pre=1，查map里1-0=1？不对，这里我用k=0的情况下，pre-k=1？还是先把逻辑写清楚。

我用具体例子来说明。nums=[1, -1, 0]，k=0。

• 初始化map:
• i=0，pre=1，查map.get(1-0)=map.get(1)，没有，count不变。更新map{0:1, 1:1}。
• i=1，pre=0，查map.get(0)=1，count=1，此时对应子数组[1,-1]。 更新map{0:2, 1:1}。
• i=2，pre=0，查map.get(0)=2，count=3。这里新增的两个子数组分别是[0]（通过之前pre=0）和[1,-1,0]？让我们验证：子数组和为0的有[1,-1]、[0]、[1,-1,0]，正好三个，count=3正确。

如果顺序反了，先在i=0时就把pre=1更新入map，虽然这次没影响，但假设nums=[1, -1]，k=0，i=1时pre=0，先更新map会把0的计数变成2，再查pre-k=0得到2，count直接算成2，但实际和为0的子数组只有[1,-1]一个，出错了。所以必须严格“先查旧账，再记新账”，不管当前pre是否在map里已经存在，都不能先更新再查询。

4. 完整代码实现与运行实测

4.1 无重复字符的最长子串：Java直接可跑版本

我日常机试练习用的是Java，因为DHU机试允许Java提交，而且Java的Scanner和HashMap用起来很顺手。这里给出我Day7留下的最终版本，完整处理了输入输出：

java复制import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        // 空字符串直接返回0，很多机试输入会带换行符，sc.nextLine()能正常处理
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int ans = 0;
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                // 取较大值，防止left回退
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            ans = Math.max(ans, right - left + 1);
        }
        System.out.println(ans);
        sc.close();
    }
}

测试一下。输入abcabcbb，代码输出3，符合预期。空字符串我没实际作为测试输入，但逻辑上ans初始为0，输出也是0，所以安全。

4.2 和为K的子数组：带注释的完整代码

java复制import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 关键初始化
        int pre = 0;
        int count = 0;
        for (int num : nums) {
            pre += num;
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        System.out.println(count);
        sc.close();
    }
}

我用几组数据实测过：

• 输入3 2回车1 1 1，输出2，对应两个[1,1]子数组，正确。
• 输入3 0回车0 0 0，输出6，这里等于三个0的排列组合3+2+1=6，代码也会得出6，正确。
• 输入1 0回车0，输出1，如果不加map.put(0,1)，这组直接输出0，属于经典错误。

4.3 滑动窗口最大值：Day7的多余题还是必背题库？

第三道题我放在Day7的附加位置。题目是给定数组nums和滑动窗口大小k，返回每个窗口的最大值。暴力法每个窗口扫描一遍是O(nk)，同样在大数据量下不可用。正确解法是维护一个双端队列，队列里存的是数组下标，并且保证队列头部永远是当前窗口最大值的下标。每次新元素入队前，把所有比它小的队尾元素弹出，再把它加进去；同时要把已经滑出窗口的下标从队头弹出。

java复制import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        Deque<Integer> deque = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            if (i >= k - 1) {
                res.add(nums[deque.peekFirst()]);
            }
        }
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i) + (i == res.size() - 1 ? "" : " "));
        }
        sc.close();
    }
}

这里有一个非常值得注意的细节：为什么弹出的条件是nums[deque.peekLast()] <= nums[i]而不是<？如果是严格小于，那么重复元素会被保留，队列里可能存在多个相同最大值，虽然结果一样，但队列长度会更长；如果写成小于等于，则重复元素中靠右的会替代靠左的，因为新元素下标更大，生命周期更长。用小于等于可以让队列尽量精简，代码更稳定。这个细节我在Day7晚上复盘时发现，属于那种“看着不影响答案，但写错会造成潜在风险”的经典机试陷阱。

4.4 三份代码的时间空间复杂度汇总

直接给一个表方便大家对照，这也是我机试备考笔记里固定要写的一项：

三道题都是O(n)级别，这也是机试算法优化的共同目标。看到一道题能想出O(n²)的朴素解法时，不要急着写，先停十秒想一想能不能通过维护某种状态把复杂度降下来。Day7三道题全部围绕这个思路展开。

5. 机试实战中的常见问题与排查技巧实录

5.1 输入输出的几个真实翻车现场

我得毫不避讳地说，Day7我至少因为输入输出浪费了半个多小时。第一个翻车是用sc.nextInt()读完数字后，再用sc.nextLine()读字符串，结果nextLine直接把缓冲区里残留的换行符读走了，字符串变成空串。解决办法是在nextInt()后面多加一个sc.nextLine()吞掉换行，或者直接用nextLine读一整行再split。第二个翻车是输出格式，题目要求每个结果占一行，我却在一道题里用print而不是println，导致所有输出挤在一行，样例对不上。

我看了一下华为OD机试的题和DHU机试这类校内评测，绝大多数都要求标准输出精确匹配，多一个空格都算错。所以你在本地练习时，一定要刻意采用“案例输入 -> 运行 -> 手动检查输出格式”的流程。我甚至会把输出重定向到文本文件里，用diff对比标准答案，这样最能发现隐形差异。

5.2 滑动窗口边界：什么时候判断窗口长度合法

写滑动窗口最大值时，最容易出错的是窗口还没有达到k的时候就往结果里添加内容，或者清理队头下标的时机不对。我的经验是分成三部曲：

1. 新元素入队前清理队尾；
2. 入队后检查队头是否已经滑出窗口，也就是下标是否小于等于i-k；
3. 当前下标达到k-1之后再收集答案。

顺序不能乱。我曾经把第二步放在第一步之前写，结果窗口还没满时就把队头弹掉了，输出全空。如果觉得绕，可以在纸上画一个长度为3的窗口手动走一遍流程，几分钟就能把逻辑捋顺。

5.3 前缀和的哈希表更新顺序，出错了怎么排查

如果发现和为K的子数组答案比预期多，多半是更新顺序问题；如果答案比预期少，多半是漏了初始化map.put(0,1)。排查时不要直接重新读一遍代码，我习惯在循环内部打印当前pre、当前count、当前map内容，用一组小数据从头走一遍。比如nums=[1,-1,0]，k=0，你会很清楚地看到count每一步怎么变化。排错要讲究“小数据+中间态输出”，而不是盯着代码发呆。

5.4 关于刷题时间和心态的管理

到了Day7，很多人会开始焦虑，觉得前六天学的好像都忘了，做题还是得翻笔记。我自己的经验是，Day7是一个坎，因为题目开始从“会做”变成“需要想一会儿才做得出来”，这种挫败感是正常的。我的建议是：每道题最多给自己二十分钟思考时间，超过就直接看题解，但看完题解必须自己手写一遍，然后隔一天再重写一次，直到能一气呵成通过全部测试数据为止。机试拼的不是智商，而是你见过的题够不够多、模板写得够不够熟。

5.5 一个额外建议：把每天的错误整理成“避坑清单”

Day7结束之后，我做了一件对后续备考帮助很大的事——把当天所有写错过的点整理成一个清单，不按题目整理，而按错误类型整理。比如“输入缓冲区换行符问题”“map更新顺序问题”“窗口边界收缩时机问题”“输出有多余空格问题”。这个避坑清单我在Day8、Day9刷题前都会快速过一遍，之后的错误率下降非常明显。备考到后期，你会发现大部分失分不是因为你不会算法，而是这些细节在反复咬人。

最后分享一点个人体会

写到这里，Day7的复盘其实已经接近尾声。我个人觉得，机试备考最忌讳的就是“刷题数量焦虑”，好像每天必须写满五道新题才算努力。其实像Day7这样，三到四道题吃透、每道题都能讲出为什么这么写、还能意识到自己踩过哪些坑，比做十道题看完答案就忘有用得多。我自己在Day7结束合上笔记的时候，抬头想了一下当天最有价值的收获，不是滑动窗口也不是前缀和，而是学会了在O(n²)解法面前先停留五秒钟，问自己一句“能不能更快”。这个习惯在后面的动态规划和贪心专题中帮我省下了大量返工时间。

如果你也正在准备DHU机试或者其他类似风格的计算机考试，不妨试试把Day7定位成一个“区间类算法专题日”，认真把滑动窗口、前缀和、单调队列这三个思路吃透，再用小数据把边界情况磨一遍。把这套流程走完，你再看之后的题目，会明显感觉到很多中等题不过是在这些基础上加了一层包装。第7天，适合开始真正触碰算法思维的核心，也适合给自己的长期备考搭一个稳当的骨架。