Google SDE 27 Intern 面经：子数组和取余等于 k + 三个 Follow-up

面试概况

Google 上来直接考 coding，干净利落！面试官是印度裔大姐，要求比较严格：讲完思路先不让写代码，问完第一个 Follow-up 才开始写，一共三个追问。

题目

给你一个正整数数组 nums 和一个整数 k，写一个函数判断 nums 中是否存在一个连续的非空子数组，满足这个子数组的和对 700001 取余等于 k。

思路：前缀和取模 + 哈希表

设前缀和 P[i] = nums[0] + ... + nums[i-1]，子数组 nums[i..j-1] 的和是 P[j] - P[i]。

条件等价于 (P[j] - P[i]) mod M == k，也就是 P[i] mod M == (P[j] - k) mod M。

遍历时维护「之前出现过的前缀和余数」集合，每到一个位置查一下 (P[j] - k) mod M 是否出现过即可。时间 O(n)。

M = 700001

def has_subarray_mod_k(nums, k, m=M):
    if not 0 <= k < m:
        return False
    seen, p = {0}, 0           # 空前缀的余数为 0
    for x in nums:
        p = (p + x) % m
        if (p - k) % m in seen:    # 先查再加入，保证子数组非空
            return True
        seen.add(p)
    return False

Follow-up 1：数组里可以出现负数了，原算法还能工作吗？

如果原算法用的是滑动窗口，那就失效了，因为有负数时窗口和不再单调。

前缀和取模的思路仍然成立，只是要保证余数非负。Python 的 % 本身返回非负数；Java / C++ 里要写成 ((p + x) % m + m) % m。

Follow-up 2：求满足条件的最短子数组长度

把集合换成哈希表，记录每个余数最近一次出现的下标，以 j 结尾的最短子数组长度就是 j - last[(P[j] - k) mod M]：

def shortest_subarray_mod_k(nums, k, m=M):
    if not 0 <= k < m:
        return -1
    last, p, best = {0: -1}, 0, float("inf")
    for j, x in enumerate(nums):
        p = (p + x) % m
        i = last.get((p - k) % m)
        if i is not None:
            best = min(best, j - i)
        last[p] = j                # 先查再更新，保证用的是更早的下标
    return -1 if best == float("inf") else best

Follow-up 3：数组长度 10⁶ 级别、内存有限，只能流式读取

上面的算法本身就是一次遍历的，不需要回看数组：状态只有当前前缀余数 p 和余数表。

余数只有 M = 700001 种，所以哈希表最多 700001 个条目，内存上界是 O(M)，和数组长度无关。还可以直接开一个长度为 M 的整数数组代替哈希表，进一步省内存。

小结

这题的关键是看出「取余」把问题变成了前缀和余数的配对。这类题目强度不小，建议自己动手写一遍，再想想每个 Follow-up 怎么接。欢迎交流解法！