题目重点：先按用户拆分两条时间有序流，再双指针求绝对时间差，明确归因方向与并列输出。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同求绝对差，同用户匹配；不强制广告先于订单，不跨用户。
- 订单侧所有用户均输出，无广告输出None；并列按(diff,order timestamp,ad timestamp)最小。正式题若要事件ID需追加稳定tie规则。
- 输入全局时间非降序，分组后仍有序；示例没有生产级乱序容忍逻辑。
解题路线
- 按user分组，禁止把全局最近的不同用户事件匹配。每组取两个有序数组，双指针比较当前时间，保留最小候选并移动较小时间一侧。
- 若a<b，固定a后面的所有广告时间≥b，与a差不可能优于当前b；所以a已经没有更优搭档，移动a安全。b<a同理；相等取得0下界，可停止。
- 并列规则需明确。示例使用字典序时间并列，由于两数组递增，首个差0也是最小相等时间；若还按事件ID排序，需处理重复timestamp的整段。
- 广告归因通常另加“广告必须在订单前”和窗口限制，这改变合同：维护每个用户最近的前序广告或用二分，而不能直接接受将来的广告。流式late event要watermark与纠正事件。
手动走一遍
训练例用户u订单[10,40]、广告[8,41]，答案差1、订单40、广告41；如果规定广告必须之前，这个答案非法，需改合同后得到(10,8)。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
def nearest_pairs(orders, ads):
"""Input (user, timestamp) lists globally sorted; ties by (diff, order, ad)."""
by_order, by_ad = defaultdict(list), defaultdict(list)
for user, time in orders:
by_order[user].append(time)
for user, time in ads:
by_ad[user].append(time)
result = {}
for user, left in by_order.items():
right = by_ad[user]
if not right:
result[user] = None
continue
i = j = 0
best = None
while i < len(left) and j < len(right):
candidate = (abs(left[i]-right[j]), left[i], right[j])
if best is None or candidate < best:
best = candidate
if left[i] < right[j]:
i += 1
elif left[i] > right[j]:
j += 1
else:
break
result[user] = best
return result
复杂度
输入共n+m项，分组与全部双指针O(n+m)，内存O(n+m)；输入已按user/time排序可按组流式处理。
易错点与追问
容易失分的边界
- 忽略用户ID做全局双指针。
- 未经确认自动将绝对差改因果归因。
- 重复时间的事件ID并列没有合同。
继续深挖
- 只允许order之前的ad怎样改？
- 每个order都要最近ad而不是每用户一对？
- 乱序流如何定义结果最终性？
