2019年前后小马智行pony.ai的校招笔试在网上讨论度一直不低。当时自动驾驶赛道正热算法岗投递量爆炸笔试筛人非常狠。这套真题二流传出来的版本我反复看过好几遍其中最典型的一道题就是经典的“和为K的连续子数组个数”。我第一次做的时候直接写了三层循环暴力解样例过了心里还挺美结果一提交就是一个大大的超时。后来复盘才发现这道题表面考的是数组题实际上考的是你能不能在一分钟内从暴力优化到哈希表以及你对边界条件的敏感程度到底有多高。这篇文章我就拿这道题做主线把完整的思考链路——从暴力解到前缀和、再到哈希表优化以及面试官视角下的考察点——全部拆开讲一遍。不光是给你一个能跑的答案更重要的是让你理解每一步优化背后的“为什么”。对正在准备自动驾驶公司算法岗的同学来说这类题目大概率不是你刷题列表里最难的一道但它刚好卡在“刷过就会、没刷过就卡”的分界线上非常能拉开差距。1. 2019年Pony.ai校招真题整体风格为什么第二题最考验基本功1.1 当年的笔试流程和配置先还原一下2019年Pony.ai校招笔试的大背景。那时候小马智行已经完成了多轮融资团队规模在扩张算法岗名额有限笔试系统用的还是牛客网那一套在线判题平台。整场笔试大概90到120分钟题量是4道左右其中第一题通常偏简单属于“送分题”第三、第四题开始上难度涉及图论、动态规划或者复杂数据结构。夹在中间的第二题就成了区分度最高的位置——基础扎实的能快速解决基础不牢的容易在暴力解上死磕到底导致后面没时间。你可能会问为什么第二题不是难到让人做不出来的那种这恰恰是出题人的策略。笔试的目的不是刁难你而是筛选出“代码能力强、思维路径清晰、能在有限时间内定位问题本质”的人。第二题的难度被刻意控制在中等水平——不能太简单让所有人都过也不能太难让所有人都挂否则区分度就没了。正因为如此这道“和为K的连续子数组个数”才在多年后依然被反复提及因为它实在是太典型了。1.2 “二”这个编号透露的题序逻辑这套真题以“二”命名说明它还有“一”。一般来说同一家公司同一年的真题会被网友整理成系列第一套收录的是笔试的第一题和第二题第二套收录的是剩下的题或者按照题面顺序编排。这个编号其实给了我们一个重要信息这道题是整套试卷中后段才出现的意味着你在做它的时候已经消耗了一部分时间和精力题感没有刚开场那么敏锐。这时候最忌讳的就是在暴力解上犹豫太久。我自己的经验是笔试中遇到这类“一眼暴力、细想哈希”的题目先花30秒确认数据规模再决定要不要直接写优化解法——如果n的范围明确超过10^4暴力基本等于自杀。1.3 最典型的第二题和为K的连续子数组个数网上流传的版本里这道题的C/Python框架都有题面大概是这样给定一个整数数组 nums 和一个整数 k请统计并返回该数组中和为 k 的连续子数组的个数。子数组要求是原数组中连续的一段。数据范围当年没有明确写但从Pony.ai一贯的出题风格推断n一般在10^4到10^5左右k可以是负数数组元素也允许负数。这个范围设定直接决定了暴力解法在笔试环境中的命运——不是不能写而是写了大概率超时一旦超时你连“部分正确”的分都拿不到因为在线判题平台对超时的处理只有一个结果TLE。2. 暴力解法先跑通能过样例但一定超时2.1 题目重述与输入输出约定我们先明确一下函数签名。按牛客网上最常见的写法class Solution: def subarraySum(self, nums: List[int], k: int) - int: pass输入是一个整数数组nums和一个整数k输出是一个整数表示连续子数组的和恰好等于k的个数。这里的关键词是“连续子数组”它和“子序列”不是一个概念——子序列不需要连续可以跳着取子数组必须是原数组中紧挨着的一段。这个限定既降低了难度也明确了枚举方式。2.2 三层循环暴力把每个子数组都算一遍第一次上手的人最容易想到的解法就是枚举所有可能的起始位置i再枚举所有可能的结束位置j最后再写一个循环把nums[i]加到nums[j]都累加一遍判断是否等于kclass Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 n len(nums) for i in range(n): for j in range(i, n): total 0 for m in range(i, j 1): total nums[m] if total k: count 1 return count这段代码的逻辑一点毛病都没有也一定能算对。问题在于性能外层有n个起点内层平均n/2个终点最内层又要算一个长度平均n/2的子数组和总时间复杂度是O(n^3)。当n10^4的时候需要执行约10^12次加法。这个量级在现代CPU上大概要跑几十分钟笔试环境根本不可能给你这个时间。还有一个隐藏问题反复对同一段区间求和做了大量重复计算这在算法竞赛中叫“重叠子问题”是典型的低效信号。2.3 两重循环优化枚举起点边走边累加稍微聪明一点的同学会想到终点的枚举和区间求和可以合并。固定起点i之后让j从i往右走同时维护一个变量current_sum每走一步就把nums[j]加进来然后立刻判断current_sum是否等于kclass Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 n len(nums) for i in range(n): current_sum 0 for j in range(i, n): current_sum nums[j] if current_sum k: count 1 return count这段代码的时间复杂度降到了O(n^2)n10^4时大约要执行5×10^7次加法在C里可能还能勉强跑完在Python里大概率还是超时。n10^5时更是完全没戏。很多同学到这里就卡住了因为他们在“已经优化过一次”的心理暗示下不太愿意继续想更优的解法。但实际上O(n^2)到O(n)的这一步才是这道题真正的分水岭。2.4 为什么暴力在笔试环境里一定被拒在线判题平台对每道题都有时间限制典型值是1秒到3秒。以1秒为例Python只能执行大约10^7次简单操作。O(n^2)的解法在n10^5时是10^10量级超时十倍百倍都不止。这还不是最要命的——最要命的是在线笔试往往还会抓作弊率和程序行为异常如果你前面几道题都很快通过只有这道题长时间卡住内心会越来越慌后面更简单的分都拿不稳。所以我建议你养成一个习惯拿到任何数组题先看数据范围。如果题目没有给出保守起见默认n是10^5或者更大直接按O(n)或O(n log n)设计。3. 前缀和数组把区间和变成两个前缀和的差3.1 一维前缀和的定义和递推公式前缀和这个概念并不复杂对于数组 nums定义 prefix[i] 为 nums[0] 到 nums[i-1] 的和也可以定义为到 nums[i] 的和看个人习惯。递推公式是prefix[0] 0 prefix[i] prefix[i-1] nums[i-1]为什么用 prefix[0]0 而不用 prefix[0]nums[0]因为这样处理可以统一边界让“从0开始的子数组”也能用同一个公式算出来。比如要求 nums[0] 到 nums[2] 的和用 prefix 表示就是 prefix[3] - prefix[0]不需要特判 i0 的情况。这是一个很小但很关键的细节很多人在笔试中因为边界问题导致下标越界或者漏算都是栽在这里。3.2 用前缀和改写判定条件子数组 nums[i] 到 nums[j] 的和等于 k等价于prefix[j1] - prefix[i] k移项之后就是prefix[j1] - k prefix[i]这个移项是整个解法的灵魂。它告诉我们当我们遍历到某个位置 j 的时候只要知道“之前出现过多少次 prefix[i] 等于当前前缀和减 k”就可以直接累加计数而不需要再回头遍历 i。这就是用空间换时间——把原本需要枚举的 i 全部记录在一张哈希表里查询变成 O(1)。3.3 哈希表登场记录“出现过的前缀和次数”具体做法是用一个哈希表map来记录“前缀和的值 - 出现的次数”然后从左到右遍历数组维护一个变量current_prefix_sum表示当前的前缀和。每到一个位置先计算target current_prefix_sum - k然后查哈希表里有多少个前缀和等于target这个数量就是“以当前位置结尾、和为 k 的子数组个数”累加到答案。最后再把当前前缀和current_prefix_sum的次数加一继续向后遍历。你可能会觉得这个顺序很讲究为什么是先查表、后更新当前前缀和的次数因为子数组要求“连续”如果先把当前前缀和加进去了万一 target 碰巧等于当前前缀和也就是 k0 的情况就会把长度为0的空子数组也算进去这显然是不对的。先查再插就能保证找出来的子数组长度至少为1。3.4 完整代码与一次遍历的写法直接看代码这个版本在 Python 和 C 里都能稳定通过大规模数据class Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 current_prefix_sum 0 prefix_sum_freq {} # 初始化前缀和0出现了一次这样才能处理从数组开头匹配到k的子数组 prefix_sum_freq[0] 1 for num in nums: current_prefix_sum num target current_prefix_sum - k if target in prefix_sum_freq: count prefix_sum_freq[target] prefix_sum_freq[current_prefix_sum] prefix_sum_freq.get(current_prefix_sum, 0) 1 return count这段代码只有一个循环时间复杂度是O(n)空间复杂度也是O(n)。用哈希表记录前缀和的频率本质上是把“历史信息”压缩存储了。你可以这样理解暴力法每一次都在重新“考古”把前面的路重新走一遍优化后的解法每走一步都留一个路标后面的人走到这里直接看路标就知道答案不用再回头。3.5 边界条件哈希表为什么要先存一个 {0: 1}初始化prefix_sum_freq[0] 1是这道题最容易漏的一步也是最容易在这个地方翻车的一步。假如数组是[1, 2, 3]k 是 3我们期望的答案是2[1,2]和[3]。当遍历到最后一个元素3时当前前缀和是6target是3。如果哈希表里没有存 prefix0 的初始值那遍历到位置2元素3的时候从0到2的前缀和等于6减去k得到3显然应该有一个从位置1到位置2的子数组满足条件——也就是子数组[1,2]。等一下这里我表述有点绕。其实{0:1}的核心作用在于当子数组从数组第一个元素开始时例如[3]这个子数组它的起点是 index2prefix[起点]prefix[2]也可以理解为0位置或者当前元素之前的和。用公式说prefix[j1] - k prefix[i]当 i0 时prefix[0]0。如果不存0所有从0开始的合法子数组就全部漏掉了这是致命的漏算。我之前见过好几个同学代码逻辑完全对就是忘了这行初始化结果样例跑出来少一个数整个人当场破防。4. 面试官视角这道题真正想考的四种能力4.1 能不能从暴力自然过渡到哈希优化如果你以为面试官只是想要一个能AC的答案那就低估这道题了。在Pony.ai这种自动驾驶公司面试官在笔试阶段看不到你的代码运行过程但他能通过你的最终代码判断你的思考习惯。一道“和为K的连续子数组”如果最后呈现的是一段三层循环暴力解哪怕能跑对小样例也很容易被打上“缺乏复杂度意识”的标签。当然笔试没有面试那种临场追问的环境所以面试官更看重的是你能不能在有限时间内找到最优解。这要求你不仅仅是背题而是要把“枚举区间和”转化为“寻找两个前缀和的差值”这个过程体现了对计算本质的理解而不是机械记忆。4.2 边界条件的敏感程度空数组、负数、k0边界条件处理是工程代码质量的预演。这道题至少有三个边界陷阱空数组nums[]时正确答案是0代码必须能直接返回0而不是报错。负数元素数组里有负数时前缀和不是单调递增的。这意味着你不能用“当前前缀和大于k就break”这种暴力优化因为后面可能出现负数把它拉回来。k0子数组的和为0如果数组是[0,0]正确答案是3[0]第一个、[0]第二个、[0,0]。哈希表初始化{0:1}配合“先查后插”的顺序就能正确算出来。但如果把插入和查询顺序搞反了就会把空子数组也算进去得到4。面试官特别爱在这种地方埋坑因为“看起来对”和“一定对”之间差的就是这些细节。自动驾驶系统对边界条件的处理更是苛刻一个边界没覆盖到了真实路测可能就是一次事故。所以这类题目虽然看起来是纯算法实际上也暗合了行业对工程师“细致程度”的高要求。4.3 空间换时间的权衡表述这道题的最优解用了一个额外哈希表空间复杂度是O(n)。有些面试风格比较老派的面试官可能会追问能不能优化到O(1)空间答案是不行。因为前缀和的值域不可预测必须存储所有出现过的前缀和才能保证不漏解。但是如果题目加一个条件——数组中所有元素都是正整数——那就有双指针/滑窗解法可以做到O(1)空间。这说明同样的题目不同的约束条件会导向完全不同的解题路径。在写代码的时候把这个考量讲清楚比闷头写一堆代码更能让面试官记住你。4.4 代码实现细节Python字典和C中map的选择很多同学在面试的时候会纠结用Python还是C。我的建议是哪个熟练用哪个但必须知道不同数据结构的时间复杂度差异。以C为例std::unordered_map的查找和插入平均是O(1)std::map是O(log n)后者基于红黑树实现会额外带有序性。这道题只需要“查值计数”用unordered_map就够了。如果误用了map时间复杂度会退化为O(n log n)虽然还是能过但会给面试官留下一个“基础不牢”的印象。Python这边dict本身就是哈希表实现直接用prefix_sum_freq.get(current_prefix_sum, 0)这种写法既简洁又安全。4.5 与自动驾驶数据处理场景的隐性关联你可能觉得一个纯数组算法题跟自动驾驶八竿子打不着。但仔细想想传感器数据流本质上就是一串连续序列计算一段时间窗口内的累计位移、累计转角、累计能耗都是“连续子数组和”的变体。比如给定一个车辆的速度序列想知道哪一段时间的累计位移最接近某个目标值这就是“和为K的连续子数组”带上位置信息后的工程版本。Pony.ai把这类题作为校招笔试倒不指望你直接用这个解法去写感知或规划模块而是考察一个工程师面对序列数据时能不能想到“用前缀和做区间统计”这个基础思维。它属于那种“平时看着没用、真正用到的时候能救命”的知识点。5. 如果题目稍微变一下五类高频变形题5.1 包含负数时哈希表依旧正确吗我们上面已经讨论了负数的情况。结论是哈希表解法不受元素正负影响因为前缀和可能出现重复但哈希表天然支持“同一个前缀和出现多次”的计数。这也正是它比双指针滑动窗口更通用的原因。双指针滑窗只在数组全为正数时有效因为和单调递增窗口可以收缩一旦有负数窗口和就不单调滑窗就废了。所以这道题只要没说明“数组元素全为正”就应该直接走向前缀和哈希表的路线不要浪费时间绕到双指针上。5.2 k0时如何快速验证你的代码k0 是最容易误判的测试用例。写一个快速测试nums [0, 0] k 0 # 期望输出3手动走一遍初始化current_prefix_sum0freq{0:1}count0第一个0current_prefix_sum0target0查表得1count1更新freq[0]2第二个0current_prefix_sum0target0查表得2count3更新freq[0]3返回3你会发现[0,0]这个子数组只在第二个0的位置被统计了一次而两个单元素[0]分别在各自位置被统计。总共3个完全正确。如果没有“先查后插”的顺序第一个0就会把空子数组也算进去count直接错乱。这种验证方式建议大家都养成习惯测试的时候别只测题目给的样例要额外测边界。5.3 求最长的和为K的子数组长度这是同一解法最自然的变形。把哈希表的值从“出现次数”改成“第一次出现的下标”每次查表时如果找到了就用当前下标减去历史下标更新最大长度。注意只记录第一次出现的下标就够了因为我们要最长的历史下标越小长度越大。这题有个细节更新哈希表时如果当前前缀和已经存在不要覆盖它保留第一次出现的位置。class Solution: def maxSubArrayLen(self, nums: List[int], k: int) - int: prefix_sum 0 first_occurrence {0: -1} max_len 0 for i, num in enumerate(nums): prefix_sum num if prefix_sum - k in first_occurrence: max_len max(max_len, i - first_occurrence[prefix_sum - k]) if prefix_sum not in first_occurrence: first_occurrence[prefix_sum] i return max_len这个变体在面试中出现频率也很高。它跟原题共享核心思想只是把“统计数量”换成了“统计跨度”。5.4 求最短且长度不小于L的和为K的子数组长度这个变体在原题基础上加了限制条件难度会上升一个档次。处理方法通常是前缀和配合单调队列或平衡树因为你要在满足长度约束的前提下寻找最接近当前前缀和减K的历史前缀和。笔试中如果遇到这种变形建议先跟面试官确认约束范围如果不能快速想出O(n)解法O(n log n)的树状数组或者有序结构也是可以接受的。重点是要让面试官看到你在“解决问题”而不是在“背诵模板”。5.5 二维矩阵中子矩阵和为K扩展到二维后暴力枚举左上角右下角是O(n^4)但可以利用前缀和矩阵压缩成一维固定上下边界把每一列的和压成一个一维数组然后对每个压缩后的数组套用本题的一维哈希表解法。整体复杂度O(n^3)。这个变形在2020年之后的笔试中出现频率明显上升很多公司喜欢拿它作为第二题的加餐。如果时间充裕建议把这道二维版本也顺手刷掉做到“一鱼多吃”。6. 我的备考建议从这道真题反推Pony.ai筛选标准6.1 笔试前一定要练熟的十类基础题从这套真题往回看Pony.ai的算法笔试并不是要你掌握特别冷门的偏题而是把最经典的题型变化出一些“工程味”。我整理了一个自测清单按重要性排序序号题型典型题目核心考点1数组区间统计和为K的子数组/前缀和哈希表优化2同向双指针最长无重复子串、最小覆盖子串窗口维护3链表快慢指针环形链表、链表中点指针移动顺序4二叉树遍历栈模拟前中后序遍历迭代与递归互转5图的最短路径Dijkstra/拓扑排序优先队列6经典DP最长递增子序列、背包问题状态定义与转移7贪心排序会议室、区间重叠排序策略8字符串匹配KMP、Trie构建前缀匹配思维9二分答案分割数组的最大值判定函数设计10模拟数学大数运算、进制转换边界与溢出处理这道“和为K的连续子数组”属于第一类也是最高频的基础题型。我建议你把每一类都选两至三道经典题刷通重点不是数量而是能否在20分钟内从暴力讲到最优解并且手写代码一次通过。6.2 代码风格审查清单面试官看一眼就会加分的小习惯很多刷题量不小的同学代码风格却是一团糟。这道题虽然逻辑简单但代码风格依然能拉开差距。我给自己定了一个检查清单每次笔试前默念一遍变量命名有意义不要用a、b、c代替current_prefix_sum但也不要冗长到一行代码写不下。函数入口处先处理明显的边界条件空数组等。注释只写“为什么”不写“是什么”。哈希表计数用get配合默认值不要手动if判断后赋值。循环内尽量少做无关操作把计算量集中在核心逻辑。这些习惯看起来无关紧要但在真实面试中面试官会在白板上直接读你的代码你的命名和结构直接影响他对你工程能力的评价。6.3 笔试时间分配不会做的题别死磕暴力保底Pony.ai的笔试题量通常控制在90分钟4道题。我的建议是前20分钟完成第一题和通读全部题目第二题最多给20分钟如果10分钟内没有清晰的优化思路就直接写一个二分或者暴力版本先保底确保至少有部分用例能过剩下的时间全部留给第三、第四题。这套策略的关键是你必须判断一道题是不是“看起来复杂、实际上简单”的类型。这道“和为K的连续子数组”就属于“看起来有点绕实际上是模板题”的类型刷过就是3分钟的事没刷过可能要卡半小时。所以多刷题的主要收益不是让你遇到原题而是让你快速识别题目类型。6.4 踩坑总结那些年我见过的高频失误最后列几个我复盘时发现的高频失误希望能帮你避坑忘记初始化{0:1}导致所有从数组开头匹配的子数组漏算。先更新前缀和频率再查表导致k0时把空子数组算进去。使用list.index()代替哈希表时间复杂度退化为O(n^2)。Python中把prefix_sum_freq[current_prefix_sum] prefix_sum_freq.get(current_prefix_sum, 0) 1写成直接1在键不存在时抛异常。过度优化在没有负数限制的前提下试图用滑动窗口结果漏解。这五个坑我每个都踩过或者亲眼见过别人踩。说实话笔试过后再看这些错误会觉得特别低级但在时间压力下大脑很容易在细节上短路。唯一有效的办法就是形成肌肉记忆把这套题的标准写法练到不需要动脑就能默写出来。我自己在实际复盘这套真题的时候最大的感触是Pony.ai并没有在题目难度上故意炫技而是在考察你有没有“把工业级问题抽象成算法模型”的直觉。一道数组题解的是传感器时间序列的统计问题一道哈希表优化的是实时系统中的查询延迟。你把它当成一道普通算法题来背只能拿到一个AC你把它理解成“如何高效处理连续数据的区间信息”才能在后面的技术面和项目面中真正拉开差距。这个思路建议你也带着去刷其他公司的真题。
2019年前后小马智行pony.ai的校招笔试在网上讨论度一直不低。当时自动驾驶赛道正热算法岗投递量爆炸笔试筛人非常狠。这套真题二流传出来的版本我反复看过好几遍其中最典型的一道题就是经典的“和为K的连续子数组个数”。我第一次做的时候直接写了三层循环暴力解样例过了心里还挺美结果一提交就是一个大大的超时。后来复盘才发现这道题表面考的是数组题实际上考的是你能不能在一分钟内从暴力优化到哈希表以及你对边界条件的敏感程度到底有多高。这篇文章我就拿这道题做主线把完整的思考链路——从暴力解到前缀和、再到哈希表优化以及面试官视角下的考察点——全部拆开讲一遍。不光是给你一个能跑的答案更重要的是让你理解每一步优化背后的“为什么”。对正在准备自动驾驶公司算法岗的同学来说这类题目大概率不是你刷题列表里最难的一道但它刚好卡在“刷过就会、没刷过就卡”的分界线上非常能拉开差距。1. 2019年Pony.ai校招真题整体风格为什么第二题最考验基本功1.1 当年的笔试流程和配置先还原一下2019年Pony.ai校招笔试的大背景。那时候小马智行已经完成了多轮融资团队规模在扩张算法岗名额有限笔试系统用的还是牛客网那一套在线判题平台。整场笔试大概90到120分钟题量是4道左右其中第一题通常偏简单属于“送分题”第三、第四题开始上难度涉及图论、动态规划或者复杂数据结构。夹在中间的第二题就成了区分度最高的位置——基础扎实的能快速解决基础不牢的容易在暴力解上死磕到底导致后面没时间。你可能会问为什么第二题不是难到让人做不出来的那种这恰恰是出题人的策略。笔试的目的不是刁难你而是筛选出“代码能力强、思维路径清晰、能在有限时间内定位问题本质”的人。第二题的难度被刻意控制在中等水平——不能太简单让所有人都过也不能太难让所有人都挂否则区分度就没了。正因为如此这道“和为K的连续子数组个数”才在多年后依然被反复提及因为它实在是太典型了。1.2 “二”这个编号透露的题序逻辑这套真题以“二”命名说明它还有“一”。一般来说同一家公司同一年的真题会被网友整理成系列第一套收录的是笔试的第一题和第二题第二套收录的是剩下的题或者按照题面顺序编排。这个编号其实给了我们一个重要信息这道题是整套试卷中后段才出现的意味着你在做它的时候已经消耗了一部分时间和精力题感没有刚开场那么敏锐。这时候最忌讳的就是在暴力解上犹豫太久。我自己的经验是笔试中遇到这类“一眼暴力、细想哈希”的题目先花30秒确认数据规模再决定要不要直接写优化解法——如果n的范围明确超过10^4暴力基本等于自杀。1.3 最典型的第二题和为K的连续子数组个数网上流传的版本里这道题的C/Python框架都有题面大概是这样给定一个整数数组 nums 和一个整数 k请统计并返回该数组中和为 k 的连续子数组的个数。子数组要求是原数组中连续的一段。数据范围当年没有明确写但从Pony.ai一贯的出题风格推断n一般在10^4到10^5左右k可以是负数数组元素也允许负数。这个范围设定直接决定了暴力解法在笔试环境中的命运——不是不能写而是写了大概率超时一旦超时你连“部分正确”的分都拿不到因为在线判题平台对超时的处理只有一个结果TLE。2. 暴力解法先跑通能过样例但一定超时2.1 题目重述与输入输出约定我们先明确一下函数签名。按牛客网上最常见的写法class Solution: def subarraySum(self, nums: List[int], k: int) - int: pass输入是一个整数数组nums和一个整数k输出是一个整数表示连续子数组的和恰好等于k的个数。这里的关键词是“连续子数组”它和“子序列”不是一个概念——子序列不需要连续可以跳着取子数组必须是原数组中紧挨着的一段。这个限定既降低了难度也明确了枚举方式。2.2 三层循环暴力把每个子数组都算一遍第一次上手的人最容易想到的解法就是枚举所有可能的起始位置i再枚举所有可能的结束位置j最后再写一个循环把nums[i]加到nums[j]都累加一遍判断是否等于kclass Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 n len(nums) for i in range(n): for j in range(i, n): total 0 for m in range(i, j 1): total nums[m] if total k: count 1 return count这段代码的逻辑一点毛病都没有也一定能算对。问题在于性能外层有n个起点内层平均n/2个终点最内层又要算一个长度平均n/2的子数组和总时间复杂度是O(n^3)。当n10^4的时候需要执行约10^12次加法。这个量级在现代CPU上大概要跑几十分钟笔试环境根本不可能给你这个时间。还有一个隐藏问题反复对同一段区间求和做了大量重复计算这在算法竞赛中叫“重叠子问题”是典型的低效信号。2.3 两重循环优化枚举起点边走边累加稍微聪明一点的同学会想到终点的枚举和区间求和可以合并。固定起点i之后让j从i往右走同时维护一个变量current_sum每走一步就把nums[j]加进来然后立刻判断current_sum是否等于kclass Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 n len(nums) for i in range(n): current_sum 0 for j in range(i, n): current_sum nums[j] if current_sum k: count 1 return count这段代码的时间复杂度降到了O(n^2)n10^4时大约要执行5×10^7次加法在C里可能还能勉强跑完在Python里大概率还是超时。n10^5时更是完全没戏。很多同学到这里就卡住了因为他们在“已经优化过一次”的心理暗示下不太愿意继续想更优的解法。但实际上O(n^2)到O(n)的这一步才是这道题真正的分水岭。2.4 为什么暴力在笔试环境里一定被拒在线判题平台对每道题都有时间限制典型值是1秒到3秒。以1秒为例Python只能执行大约10^7次简单操作。O(n^2)的解法在n10^5时是10^10量级超时十倍百倍都不止。这还不是最要命的——最要命的是在线笔试往往还会抓作弊率和程序行为异常如果你前面几道题都很快通过只有这道题长时间卡住内心会越来越慌后面更简单的分都拿不稳。所以我建议你养成一个习惯拿到任何数组题先看数据范围。如果题目没有给出保守起见默认n是10^5或者更大直接按O(n)或O(n log n)设计。3. 前缀和数组把区间和变成两个前缀和的差3.1 一维前缀和的定义和递推公式前缀和这个概念并不复杂对于数组 nums定义 prefix[i] 为 nums[0] 到 nums[i-1] 的和也可以定义为到 nums[i] 的和看个人习惯。递推公式是prefix[0] 0 prefix[i] prefix[i-1] nums[i-1]为什么用 prefix[0]0 而不用 prefix[0]nums[0]因为这样处理可以统一边界让“从0开始的子数组”也能用同一个公式算出来。比如要求 nums[0] 到 nums[2] 的和用 prefix 表示就是 prefix[3] - prefix[0]不需要特判 i0 的情况。这是一个很小但很关键的细节很多人在笔试中因为边界问题导致下标越界或者漏算都是栽在这里。3.2 用前缀和改写判定条件子数组 nums[i] 到 nums[j] 的和等于 k等价于prefix[j1] - prefix[i] k移项之后就是prefix[j1] - k prefix[i]这个移项是整个解法的灵魂。它告诉我们当我们遍历到某个位置 j 的时候只要知道“之前出现过多少次 prefix[i] 等于当前前缀和减 k”就可以直接累加计数而不需要再回头遍历 i。这就是用空间换时间——把原本需要枚举的 i 全部记录在一张哈希表里查询变成 O(1)。3.3 哈希表登场记录“出现过的前缀和次数”具体做法是用一个哈希表map来记录“前缀和的值 - 出现的次数”然后从左到右遍历数组维护一个变量current_prefix_sum表示当前的前缀和。每到一个位置先计算target current_prefix_sum - k然后查哈希表里有多少个前缀和等于target这个数量就是“以当前位置结尾、和为 k 的子数组个数”累加到答案。最后再把当前前缀和current_prefix_sum的次数加一继续向后遍历。你可能会觉得这个顺序很讲究为什么是先查表、后更新当前前缀和的次数因为子数组要求“连续”如果先把当前前缀和加进去了万一 target 碰巧等于当前前缀和也就是 k0 的情况就会把长度为0的空子数组也算进去这显然是不对的。先查再插就能保证找出来的子数组长度至少为1。3.4 完整代码与一次遍历的写法直接看代码这个版本在 Python 和 C 里都能稳定通过大规模数据class Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 current_prefix_sum 0 prefix_sum_freq {} # 初始化前缀和0出现了一次这样才能处理从数组开头匹配到k的子数组 prefix_sum_freq[0] 1 for num in nums: current_prefix_sum num target current_prefix_sum - k if target in prefix_sum_freq: count prefix_sum_freq[target] prefix_sum_freq[current_prefix_sum] prefix_sum_freq.get(current_prefix_sum, 0) 1 return count这段代码只有一个循环时间复杂度是O(n)空间复杂度也是O(n)。用哈希表记录前缀和的频率本质上是把“历史信息”压缩存储了。你可以这样理解暴力法每一次都在重新“考古”把前面的路重新走一遍优化后的解法每走一步都留一个路标后面的人走到这里直接看路标就知道答案不用再回头。3.5 边界条件哈希表为什么要先存一个 {0: 1}初始化prefix_sum_freq[0] 1是这道题最容易漏的一步也是最容易在这个地方翻车的一步。假如数组是[1, 2, 3]k 是 3我们期望的答案是2[1,2]和[3]。当遍历到最后一个元素3时当前前缀和是6target是3。如果哈希表里没有存 prefix0 的初始值那遍历到位置2元素3的时候从0到2的前缀和等于6减去k得到3显然应该有一个从位置1到位置2的子数组满足条件——也就是子数组[1,2]。等一下这里我表述有点绕。其实{0:1}的核心作用在于当子数组从数组第一个元素开始时例如[3]这个子数组它的起点是 index2prefix[起点]prefix[2]也可以理解为0位置或者当前元素之前的和。用公式说prefix[j1] - k prefix[i]当 i0 时prefix[0]0。如果不存0所有从0开始的合法子数组就全部漏掉了这是致命的漏算。我之前见过好几个同学代码逻辑完全对就是忘了这行初始化结果样例跑出来少一个数整个人当场破防。4. 面试官视角这道题真正想考的四种能力4.1 能不能从暴力自然过渡到哈希优化如果你以为面试官只是想要一个能AC的答案那就低估这道题了。在Pony.ai这种自动驾驶公司面试官在笔试阶段看不到你的代码运行过程但他能通过你的最终代码判断你的思考习惯。一道“和为K的连续子数组”如果最后呈现的是一段三层循环暴力解哪怕能跑对小样例也很容易被打上“缺乏复杂度意识”的标签。当然笔试没有面试那种临场追问的环境所以面试官更看重的是你能不能在有限时间内找到最优解。这要求你不仅仅是背题而是要把“枚举区间和”转化为“寻找两个前缀和的差值”这个过程体现了对计算本质的理解而不是机械记忆。4.2 边界条件的敏感程度空数组、负数、k0边界条件处理是工程代码质量的预演。这道题至少有三个边界陷阱空数组nums[]时正确答案是0代码必须能直接返回0而不是报错。负数元素数组里有负数时前缀和不是单调递增的。这意味着你不能用“当前前缀和大于k就break”这种暴力优化因为后面可能出现负数把它拉回来。k0子数组的和为0如果数组是[0,0]正确答案是3[0]第一个、[0]第二个、[0,0]。哈希表初始化{0:1}配合“先查后插”的顺序就能正确算出来。但如果把插入和查询顺序搞反了就会把空子数组也算进去得到4。面试官特别爱在这种地方埋坑因为“看起来对”和“一定对”之间差的就是这些细节。自动驾驶系统对边界条件的处理更是苛刻一个边界没覆盖到了真实路测可能就是一次事故。所以这类题目虽然看起来是纯算法实际上也暗合了行业对工程师“细致程度”的高要求。4.3 空间换时间的权衡表述这道题的最优解用了一个额外哈希表空间复杂度是O(n)。有些面试风格比较老派的面试官可能会追问能不能优化到O(1)空间答案是不行。因为前缀和的值域不可预测必须存储所有出现过的前缀和才能保证不漏解。但是如果题目加一个条件——数组中所有元素都是正整数——那就有双指针/滑窗解法可以做到O(1)空间。这说明同样的题目不同的约束条件会导向完全不同的解题路径。在写代码的时候把这个考量讲清楚比闷头写一堆代码更能让面试官记住你。4.4 代码实现细节Python字典和C中map的选择很多同学在面试的时候会纠结用Python还是C。我的建议是哪个熟练用哪个但必须知道不同数据结构的时间复杂度差异。以C为例std::unordered_map的查找和插入平均是O(1)std::map是O(log n)后者基于红黑树实现会额外带有序性。这道题只需要“查值计数”用unordered_map就够了。如果误用了map时间复杂度会退化为O(n log n)虽然还是能过但会给面试官留下一个“基础不牢”的印象。Python这边dict本身就是哈希表实现直接用prefix_sum_freq.get(current_prefix_sum, 0)这种写法既简洁又安全。4.5 与自动驾驶数据处理场景的隐性关联你可能觉得一个纯数组算法题跟自动驾驶八竿子打不着。但仔细想想传感器数据流本质上就是一串连续序列计算一段时间窗口内的累计位移、累计转角、累计能耗都是“连续子数组和”的变体。比如给定一个车辆的速度序列想知道哪一段时间的累计位移最接近某个目标值这就是“和为K的连续子数组”带上位置信息后的工程版本。Pony.ai把这类题作为校招笔试倒不指望你直接用这个解法去写感知或规划模块而是考察一个工程师面对序列数据时能不能想到“用前缀和做区间统计”这个基础思维。它属于那种“平时看着没用、真正用到的时候能救命”的知识点。5. 如果题目稍微变一下五类高频变形题5.1 包含负数时哈希表依旧正确吗我们上面已经讨论了负数的情况。结论是哈希表解法不受元素正负影响因为前缀和可能出现重复但哈希表天然支持“同一个前缀和出现多次”的计数。这也正是它比双指针滑动窗口更通用的原因。双指针滑窗只在数组全为正数时有效因为和单调递增窗口可以收缩一旦有负数窗口和就不单调滑窗就废了。所以这道题只要没说明“数组元素全为正”就应该直接走向前缀和哈希表的路线不要浪费时间绕到双指针上。5.2 k0时如何快速验证你的代码k0 是最容易误判的测试用例。写一个快速测试nums [0, 0] k 0 # 期望输出3手动走一遍初始化current_prefix_sum0freq{0:1}count0第一个0current_prefix_sum0target0查表得1count1更新freq[0]2第二个0current_prefix_sum0target0查表得2count3更新freq[0]3返回3你会发现[0,0]这个子数组只在第二个0的位置被统计了一次而两个单元素[0]分别在各自位置被统计。总共3个完全正确。如果没有“先查后插”的顺序第一个0就会把空子数组也算进去count直接错乱。这种验证方式建议大家都养成习惯测试的时候别只测题目给的样例要额外测边界。5.3 求最长的和为K的子数组长度这是同一解法最自然的变形。把哈希表的值从“出现次数”改成“第一次出现的下标”每次查表时如果找到了就用当前下标减去历史下标更新最大长度。注意只记录第一次出现的下标就够了因为我们要最长的历史下标越小长度越大。这题有个细节更新哈希表时如果当前前缀和已经存在不要覆盖它保留第一次出现的位置。class Solution: def maxSubArrayLen(self, nums: List[int], k: int) - int: prefix_sum 0 first_occurrence {0: -1} max_len 0 for i, num in enumerate(nums): prefix_sum num if prefix_sum - k in first_occurrence: max_len max(max_len, i - first_occurrence[prefix_sum - k]) if prefix_sum not in first_occurrence: first_occurrence[prefix_sum] i return max_len这个变体在面试中出现频率也很高。它跟原题共享核心思想只是把“统计数量”换成了“统计跨度”。5.4 求最短且长度不小于L的和为K的子数组长度这个变体在原题基础上加了限制条件难度会上升一个档次。处理方法通常是前缀和配合单调队列或平衡树因为你要在满足长度约束的前提下寻找最接近当前前缀和减K的历史前缀和。笔试中如果遇到这种变形建议先跟面试官确认约束范围如果不能快速想出O(n)解法O(n log n)的树状数组或者有序结构也是可以接受的。重点是要让面试官看到你在“解决问题”而不是在“背诵模板”。5.5 二维矩阵中子矩阵和为K扩展到二维后暴力枚举左上角右下角是O(n^4)但可以利用前缀和矩阵压缩成一维固定上下边界把每一列的和压成一个一维数组然后对每个压缩后的数组套用本题的一维哈希表解法。整体复杂度O(n^3)。这个变形在2020年之后的笔试中出现频率明显上升很多公司喜欢拿它作为第二题的加餐。如果时间充裕建议把这道二维版本也顺手刷掉做到“一鱼多吃”。6. 我的备考建议从这道真题反推Pony.ai筛选标准6.1 笔试前一定要练熟的十类基础题从这套真题往回看Pony.ai的算法笔试并不是要你掌握特别冷门的偏题而是把最经典的题型变化出一些“工程味”。我整理了一个自测清单按重要性排序序号题型典型题目核心考点1数组区间统计和为K的子数组/前缀和哈希表优化2同向双指针最长无重复子串、最小覆盖子串窗口维护3链表快慢指针环形链表、链表中点指针移动顺序4二叉树遍历栈模拟前中后序遍历迭代与递归互转5图的最短路径Dijkstra/拓扑排序优先队列6经典DP最长递增子序列、背包问题状态定义与转移7贪心排序会议室、区间重叠排序策略8字符串匹配KMP、Trie构建前缀匹配思维9二分答案分割数组的最大值判定函数设计10模拟数学大数运算、进制转换边界与溢出处理这道“和为K的连续子数组”属于第一类也是最高频的基础题型。我建议你把每一类都选两至三道经典题刷通重点不是数量而是能否在20分钟内从暴力讲到最优解并且手写代码一次通过。6.2 代码风格审查清单面试官看一眼就会加分的小习惯很多刷题量不小的同学代码风格却是一团糟。这道题虽然逻辑简单但代码风格依然能拉开差距。我给自己定了一个检查清单每次笔试前默念一遍变量命名有意义不要用a、b、c代替current_prefix_sum但也不要冗长到一行代码写不下。函数入口处先处理明显的边界条件空数组等。注释只写“为什么”不写“是什么”。哈希表计数用get配合默认值不要手动if判断后赋值。循环内尽量少做无关操作把计算量集中在核心逻辑。这些习惯看起来无关紧要但在真实面试中面试官会在白板上直接读你的代码你的命名和结构直接影响他对你工程能力的评价。6.3 笔试时间分配不会做的题别死磕暴力保底Pony.ai的笔试题量通常控制在90分钟4道题。我的建议是前20分钟完成第一题和通读全部题目第二题最多给20分钟如果10分钟内没有清晰的优化思路就直接写一个二分或者暴力版本先保底确保至少有部分用例能过剩下的时间全部留给第三、第四题。这套策略的关键是你必须判断一道题是不是“看起来复杂、实际上简单”的类型。这道“和为K的连续子数组”就属于“看起来有点绕实际上是模板题”的类型刷过就是3分钟的事没刷过可能要卡半小时。所以多刷题的主要收益不是让你遇到原题而是让你快速识别题目类型。6.4 踩坑总结那些年我见过的高频失误最后列几个我复盘时发现的高频失误希望能帮你避坑忘记初始化{0:1}导致所有从数组开头匹配的子数组漏算。先更新前缀和频率再查表导致k0时把空子数组算进去。使用list.index()代替哈希表时间复杂度退化为O(n^2)。Python中把prefix_sum_freq[current_prefix_sum] prefix_sum_freq.get(current_prefix_sum, 0) 1写成直接1在键不存在时抛异常。过度优化在没有负数限制的前提下试图用滑动窗口结果漏解。这五个坑我每个都踩过或者亲眼见过别人踩。说实话笔试过后再看这些错误会觉得特别低级但在时间压力下大脑很容易在细节上短路。唯一有效的办法就是形成肌肉记忆把这套题的标准写法练到不需要动脑就能默写出来。我自己在实际复盘这套真题的时候最大的感触是Pony.ai并没有在题目难度上故意炫技而是在考察你有没有“把工业级问题抽象成算法模型”的直觉。一道数组题解的是传感器时间序列的统计问题一道哈希表优化的是实时系统中的查询延迟。你把它当成一道普通算法题来背只能拿到一个AC你把它理解成“如何高效处理连续数据的区间信息”才能在后面的技术面和项目面中真正拉开差距。这个思路建议你也带着去刷其他公司的真题。
)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
