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