Google New Grad 的编程轮爱在经典套路上做包装，这道"子数组和取余等于 k"就是典型：题面绕一点，但本质是前缀和余数 + 哈希。这篇按 oavoservice 学员的 Google NG 复盘，把这道题从暴力到最优一步步讲清楚。文末附 VO辅助 / VO代面 的对接路径，给正在校招、转码、后端开发求职的同学一个实战参考。
一、Google NG 编程轮概览
| 维度 | 详情 |
|---|---|
| 形式 | 远程视频，单轮约 45 分钟 |
| 题量 | 1 道编程题 + 追问 |
| 语言 | 自选，Python / Java / C++ 常见 |
| 考察 | 前缀和 / 哈希、复杂度优化、边界处理、沟通 |
| 风格 | 经典题变体，考你能不能认出底层套路 |
Google NG 的题难度集中在 LeetCode 中等。重点不在题新，而在你能不能快速认出"这其实是哪个经典套路的变形"，并干净地实现出来。
二、题目
给一个正整数数组 nums 和整数 k，写一个函数判断：nums 中是否存在一个连续的非空子数组，其元素之和对 6,000,009 取余后等于 k。
三、拆题：取余 + 子数组和 → 前缀和余数
"连续子数组的和"第一反应就是前缀和：子数组 (i, j] 的和等于 prefix[j] - prefix[i]。现在要的是这个差对 M = 6_000_009 取余等于 k，即：
(prefix[j] - prefix[i]) % M == k
整理一下：prefix[j] % M 和 prefix[i] % M 之间相差 k（在模 M 意义下）。所以一边遍历一边把见过的前缀和余数丢进哈希集合，对当前余数 cur，只要集合里存在 (cur - k) % M，就说明存在满足条件的子数组。
朴素思路（对照）
枚举所有 (i, j) 区间求和取余，O(n²) 甚至 O(n³)。数据一大就超时，仅用于验证小用例。
最优解：前缀和余数 + 哈希
注意子数组非空：要先处理当前元素、更新 cur，再判断，且初始要把"空前缀"的余数 0 放进集合，覆盖"从头开始的子数组"这种情况。
def HasSubarrayKMod(nums, k):
M = 6_000_009
k %= M
seen = {0} # 空前缀的余数，覆盖从头开始的子数组
cur = 0
for x in nums:
cur = (cur + x) % M
if (cur - k) % M in seen:
return True
seen.add(cur)
return False
print(HasSubarrayKMod([2, 3, 5], 8)) # True，子数组 [3,5] 和为 8
print(HasSubarrayKMod([2, 3, 5], 100)) # False
时间复杂度：O(n)（一次遍历，哈希均摊 O(1)）。空间复杂度：O(n)（最多存 n+1 个余数）。
四、临场提醒
- 看到"取余 + 子数组和"先往前缀和余数 + 哈希上靠，几乎是这类题的标准解。
- 先把"空前缀余数 0"放进集合，否则会漏掉"从头开始的子数组"这种边界。
- 取余要对
k也先取模，避免k超出[0, M)时判定出错。 - 先口头讲清"为什么是前缀和之差"，再动手，给面试官清晰的推理过程。
FAQ
Q1：这道题为什么用前缀和余数？
因为子数组和 = 两个前缀和之差，再叠加取余，问题就变成"是否存在两个前缀和余数相差 k（模 M）"。一遍遍历把见过的余数存进哈希集合即可 O(n) 判定，比枚举所有子数组的 O(n²) 高效得多。
Q2：为什么初始集合要放一个 0？
0 代表"空前缀"的余数。它能覆盖"子数组正好从下标 0 开始"的情况——此时当前前缀和余数本身就等于 k，需要和空前缀做差才能判定。
Q3：模数是 6,000,009 这种奇怪的数有影响吗？
没有，算法对任意正模数 M 都成立。具体数值只影响余数范围，不改变前缀和余数 + 哈希的思路。
Q4：Google NG 编程轮怎么高效准备？
按前缀和 / 哈希、双指针、图与树遍历、DP 分专题刷，每类限时练并口头讲思路。需要按 Google NG 题型做限时 mock、逐题讲解或 VO辅助 / VO代面 全程对接，可以走下面的路径定制。
正在准备 Google NG 面试？
Google NG 编程轮爱考经典题变体，吃的是套路识别和清晰表达。oavoservice 提供 Google 全流程陪练：前缀和 / 哈希 / 图与树遍历 / DP 高频题限时模拟，拆题与口头表达逐题打磨，按 NG 校招题型做预测。教练含大厂资深工程师，支持 VO辅助 / VO代面 全程对接。
立即添加微信 Coding0201，获取 Google 真题与陪练。
联系方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy