近日，csoahelp 收到一道 Snowflake Coding Round 面试真题。题目从两个有序数组的组合计数出发，并进一步延伸到三个有序数组的 follow-up。

英文原题

You are given two sorted arrays A and B, and an integer D.

Find the number of pairs (i, j) such that:

|A[i] - B[j]| <= D

面试官首先要求统计两个有序数组中，差值不超过 D 的下标对数量。

Follow-up

You are given three sorted arrays A, B and C, and an integer D.

Find the number of tuples (i, j, k) such that:

|A[i] - B[j]| <= D
|A[i] - C[k]| <= D
|B[j] - C[k]| <= D

也就是说，需要从三个数组中各选择一个元素，使任意两个元素之间的差值都不超过 D。题目允许出现重复数字，并按照下标组合计数。

示例

A = [1, 2]
B = [2]
C = [1, 3]
D = 1

满足条件的三元组共有三个：

(1, 2, 1)
(2, 2, 1)
(2, 2, 3)

因此返回：

3

解题思路

第一问可以利用数组已经排序的特点，对数组 B 维护两个单调移动的指针。

对于每个 A[i]，找到 B 中位于以下范围的元素：

A[i] - D <= B[j] <= A[i] + D

假设合法区间为 [left, right)，那么当前元素贡献的答案就是：

right - left

两个指针在整个过程中只向右移动，因此时间复杂度为：

O(A.length + B.length)

如果 follow-up 改成 A 无序、B 有序，可以对每个 A[i] 在 B 中分别执行 lower_bound 和 upper_bound，复杂度变为：

O(A.length × log B.length)

三数组 Follow-up

三个条件其实可以转换成一个更容易处理的条件：

max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]) <= D

因为只要三个数字中的最大值和最小值之差不超过 D，中间数字与另外两个数字的差值也一定不会超过 D。这一步等价转换也是面试官重点追问的部分。

接下来可以把三个有序数组合并成一个有序序列，同时记录每个数字来自 A、B 还是 C。

在合并后的序列上维护滑动窗口，使窗口始终满足：

values[right] - values[left] <= D

同时记录窗口内来自三个数组的元素数量：

countA
countB
countC

当当前元素来自 A 时，它可以和窗口内任意一个 B、任意一个 C 组成三元组，因此新增：

countB × countC

当前元素来自 B 时新增：

countA × countC

当前元素来自 C 时新增：

countA × countB

把当前元素视为这个三元组中最后被扫描到的最大元素，可以保证每个合法三元组只会被统计一次。面试中的实现也是通过来源计数数组和滑动窗口完成统计。

实现复杂度为：

Time:  O(A.length + B.length + C.length)
Space: O(A.length + B.length + C.length)

面试容易出错的地方

这道题真正的难点不是写出三层循环，而是快速识别出：

两两差值 <= D

等价于：

最大值 - 最小值 <= D

另外还需要注意重复数字按照不同下标组合分别计数；计算答案时使用 long，避免组合数量超过 int；测试时应覆盖空数组、D = 0、大量重复元素以及负数。

csoahelp 面试辅助

Snowflake 这道题的 follow-up 比第一问更重要。面试官会不断要求候选人解释等价条件、统计方式以及为什么不会重复计数。

csoahelp 提供面试实时文本辅助和 Mock Interview，能够在面试过程中帮助整理题意、分析 follow-up、补充复杂度和测试用例，让回答更加完整、有条理。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~