Snowflake OA 面试真题解析：Find Number of Pairs and Tuples Within a Threshold

题目描述

给定两个有序数组 A、B 和一个整数 D，求满足 |A[i] - B[j]| <= D 的配对 (i, j) 数量。追问通常是把两个数组扩展到更多个，统计满足阈值关系的元组。

解题思路

对每个 A[i]，在 B 中找出满足 B[j] >= A[i] - D 的下界，以及 B[j] <= A[i] + D 的上界，中间的元素都合法。由于 B 有序，用二分或双指针维护一个单调窗口，统计落入 [A[i]-D, A[i]+D] 的 B 元素个数。

import bisect

def count_pairs(A, B, D):
    ans = 0
    for a in A:
        lo = bisect.bisect_left(B, a - D)
        hi = bisect.bisect_right(B, a + D)
        ans += hi - lo
    return ans

复杂度与易错点

对每个 A[i] 二分，时间 O(m log n)；若用双指针，可做到 O(m + n)。注意使用 bisect_left 处理等于下界的元素、bisect_right 处理等于上界的元素，避免边界漏计或重复计。

FAQ

为什么下界用 bisect_left、上界用 bisect_right？

|A[i] - B[j]| <= D 是闭区间，等于两端边界的元素都应计入，所以下界取左闭、上界取右闭。

参考来源

• LeetCode 167 — Two Sum II
• LeetCode 532 — K-diff Pairs in an Array

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。