一个已排序的 int32 数组，长度 10^7（约 40MB），判断是否存在 i<j 使 a[i]+a[j] = target。方案 A：双指针；方案 B：哈希表。两者时间都是 O(n)，你选哪个？从访存模式、内存开销、最坏情况三个角度说明。如果要求输出所有不重复的数对呢？

面试官在考什么

考察在渐进复杂度相同时，能否用常数因子、访存局部性和额外内存成本做工程选型。

双指针

回答框架 · 前两步

1. 双指针：左右指针从两端相向移动，和偏小就右移左指针、偏大就左移右指针；O(n) 时间、O(1) 额外空间，且是顺序访存，cache 友好。
2. 哈希表：O(n) 时间但需要 O(n) 额外内存（10^7 个 int 的哈希表通常上百 MB 量级），且随机访存 cache miss 高。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 一个 N×N 的 0/1 网格，N=2000（共 400 万格），0 表示可通行，1 表示障碍，允许上下左右四方向移动，每走一格算 1 步。要求从 (0,0) 走到 (N-1,N-1)，给出最短步数，不可达返回 -1。内存上限 256MB。请说明你选 BFS 还是 DFS、队列和 visited 怎么设计、以及 visited 具体在什么时刻打标记。
• 社交关系图共 10^9 个用户，平均出度 200，边存放在分布式 KV 上（一次邻居查询约 5ms），单机可用内存 64GB。现在要找出指定用户 A 的 3 度以内（含 3 度）的全部用户 ID。你选 BFS 还是 DFS？写出你的遍历控制逻辑，估算 frontier（当前层待扩展集合）的最大规模，并说明用什么结构做去重。
• 你接手一个权限可达性服务：授权图约 500 万节点、2000 万条有向边（用户→角色→权限组→资源），业务上允许成环。线上要回答『用户 u 能否到达资源 r』，峰值 10 万 QPS、P99 要求 20ms。上一版实现是每次请求从 u 出发做一次 DFS，线上大面积超时并偶发栈溢出。请给出你的方案、演进路径和取舍。
• 给你一个 1000×1000 的 0/1 网格（1 是陆地，0 是水），上下左右相邻的陆地属于同一个岛，要求返回岛屿数量。A 同学用递归 DFS 做 flood fill，样例全过，但把规模放大到接近满屏陆地时程序崩溃。请说明崩溃的原因，写出你会怎么改；并说明同一份数据用 BFS 写时，队列规模的最坏情况是什么量级。
• 有向图有 4 个节点 s、a、b、t，边和权值是：s→a = 1，s→b = 2，b→a = -2，a→t = 3，b→t = 10。用朴素 Dijkstra（每次从未确定的节点里取 dist 最小的那个标记为已确定，之后不再更新它的 dist）从 s 求到 t 的最短路。请说出它算出的 dist[t] 是多少、正确答案是多少、差在哪一步上，然后说明什么样的图 Dijkstra 才是安全的。
• 一个城市路网约 10^8 个节点、2.5×10^8 条边，边权是通行时间（非负，但按早晚高峰每 5 分钟整体更新一次）。要支持单点到单点最短路查询、峰值 10^4 QPS、P99 延迟 < 50ms。朴素 Dijkstra 单次查询要扫描大量节点。你怎么选算法与架构？说清预处理成本、查询延迟、以及权重频繁变化带来的矛盾怎么权衡。