秋招算法高频精讲：双指针与有序数组求交集深度复盘（含极端数据与工程追问）#

Author#

📌 真实面试背景#

在 值得买科技 等互联网与游戏大厂的算法与工程岗技术面试中，面试官经常以看似简单的基础题作为引子，层层设套考察应聘者的边界处理能力、复杂度敏感度、极端规模优化意识（ $M \ll N$ ）以及海量数据工程落地思维（大数据外排序）。

面试真题还原：
给定两个单调递增的有序数组 $A$ （长度 $M$ ）和 $B$ （长度 $N$ ），数组中可能存在重复元素，要求找出两数组中数值相同的公共元素集合（下标可以不同）。

本文将从最朴素的双指针算法出发，剖析 4 种演进方案，并深入探讨 C++ STL 内部实现与海量数据外存流式处理。

目录#

一、算法一：标准双指针扫描法（Baseline）
二、算法二：极不平衡规模优化——二分查找法（ $M \ll N$ ）
三、算法三：指数跳跃搜索（Galloping / Exponential Search）
四、算法四：海量数据与外排序流式处理（Memory Constraint）
五、重复元素处理策略与 STL 源码对比
六、完整 C++ 工业级工程实现

一、算法一：标准双指针扫描法（Baseline）#

1. 核心数学原理#

由于数组 $A$ 和 $B$ 均已升序排列，数组元素具有严格的单调性： $\forall i_1 < i_2 \implies A[i_1] \le A[i_2]$

利用此性质，我们可以维护两个指针 $i$ 和 $j$ ，分别从 $A[0]$ 和 $B[0]$ 出发：

若 $A[i] == B[j]$ ：找到一个公共值，记录该值，随后 $i++, j++$ 。
若 $A[i] < B[j]$ ：说明当前 $A[i]$ 小于 $B[j]$ 及 $B$ 中后续所有元素，在 $B$ 中绝无匹配可能，必须右移 $i$ （ $i++$ ）。
若 $A[i] > B[j]$ ：同理， $B[j]$ 小于 $A[i]$ 及 $A$ 中后续元素，必须右移 $j$ （ $j++$ ）。
循环终止条件： $i \ge M$ 或 $j \ge N$ 。

1
数组 A: [ 1,  3,  4,  7,  9,  11 ]
2
          ↑ i
3
数组 B: [ 2,  3,  5,  7,  8,  9,  12 ]
4
          ↑ j
5

6
Step 1: A[0]=1 < B[0]=2  --> i++
7
Step 2: A[1]=3 == B[0]=3 --> Match 3! i++, j++
8
Step 3: A[2]=4 < B[1]=5  --> i++
9
Step 4: A[3]=7 > B[1]=5  --> j++
10
Step 5: A[3]=7 == B[2]=7 --> Match 7! i++, j++
11
...

2. 复杂度分析#

时间复杂度： $\mathcal{O}(M + N)$ 。每个指针至多移动各自数组长度的次数。
空间复杂度： $\mathcal{O}(1)$ （仅需常数级别的指针变量，不计输出数组）。

二、算法二：极不平衡规模优化——二分查找法（ $M \ll N$ ）#

1. 痛点：为什么双指针不是万能的？#

假设 $M = 10$ （短数组），而 $N = 10^8$ （超长数组）。

双指针法：需要逐步推进 $j$ 指针遍历长数组，运算次数约 $10^8$ 次。
二分查找优化：遍历短数组 $A$ $A$ 中的每一个元素 $A[i]$ $A [i]$ ，在长数组 $B$ $B$ 中执行二分查找（Binary Search / std::lower_bound）。
- 单次二分查找耗时 $\mathcal{O}(\log N) = \log_2(10^8) \approx 27$ 次比较。
- $10$ 个元素总共仅需 $10 \times 27 = 270$ 次比较！
- 加速比超过 370,000 倍！

2. 复杂度#

时间复杂度： $\mathcal{O}(M \log N)$ （当 $M \log N < M + N$ ，即 $M \ll N$ 时显著占优）。
空间复杂度： $\mathcal{O}(1)$ 。

三、算法三：指数跳跃搜索（Galloping / Exponential Search）#

在二分查找的基础上，如果短数组 $A$ 中的元素也是递增且分布相对聚集的，我们可以进一步利用上一轮在 $B$ 中找到的位置作为下界起点，并结合倍增跳跃（Galloping Search）：

寻找查找上界：检查 $B[\text{offset} + 1], B[\text{offset} + 2], B[\text{offset} + 4], \dots, B[\text{offset} + 2^k]$ 。
确定区间后，仅在 $[2^{k-1}, 2^k]$ 这个极小区间内执行二分查找。
将时间复杂度进一步平摊至 $\mathcal{O}\left(M \log \frac{N}{M}\right)$ 。著名的 Python / Java 默认排序算法 Timsort 在归并阶段即大量采用了此策略。

四、算法四：海量数据与外排序流式处理（Memory Constraint）#

1. 极端场景：数组数据无法一次性放入内存#

面试官追问：如果文件 $A$ 和文件 $B$ 各有 $100\text{GB}$ 且均已排序存放在磁盘上，而当前服务器物理内存仅有 $2\text{GB}$ ，如何高效求交集？

2. 流式归并方案（Block-based Streaming Merge）#

由于两个文件本身已经全局有序，我们完全不需要将全量数据加载到内存：

缓冲区开辟：在内存中为文件 $A$ 开辟输入缓冲区 BufA（如 64MB），为文件 $B$ 开辟输入缓冲区 BufB（如 64MB），并开辟一个输出缓冲区 BufOut（如 64MB）。
块级加载：从文件 $A, B$ 各自读取第一块数据至缓冲区。
双指针流式比对：
- 指针在 BufA 和 BufB 内部按算法一的规则比对。
- 当 BufA 的游标耗尽时，触发磁盘 I/O 顺序读取 $A$ 的下一块（fread / read）。
- 当 BufB 的游标耗尽时，读取 $B$ 的下一块。
- 匹配到的元素写入 BufOut，满 64MB 批量刷盘（fwrite）。
性能优势：
- 内存占用严格恒定为 $\mathcal{O}(1)$ （即 $3 \times 64\text{MB} = 192\text{MB}$ ）。
- 磁盘 I/O 全部为最高效的顺序流式读取（Sequential I/O），充分利用 OS Page Cache 与磁盘预读机制。

五、重复元素处理策略与 STL 源码对比#

1. 去重（Unique Elements Only） vs 保留多重频次（Multi-set Intersection）#

面试中必须主动向面试官确认对于重复元素的定义：

LeetCode 349（去重集合交集）：两数组若都有多个 3，结果集仅保留一个 3。
- 处理：匹配后，利用 while (i + 1 < M && A[i] == A[i + 1]) i++; 跳过所有重复项。
LeetCode 350（多重集合交集）：若 $A$ $A$ 有 3 个 3， $B$ $B$ 有 2 个 3，结果集保留 $\min(3, 2) = 2$ $min (3, 2) = 2$ 个 3。
- 处理：每次匹配一个元素，两个指针同时向后自增 1（ $i++, j++$ ）。

2. C++ STL `std::set_intersection` 源码核心剖析#

在 <algorithm> 头文件中，STL 官方实现即采用了标准双指针设计：

1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
3
                                InputIterator2 first2, InputIterator2 last2,
4
                                OutputIterator result) {
5
    while (first1 != last1 && first2 != last2) {
6
        if (*first1 < *first2) {
7
            ++first1;
8
        } else if (*first2 < *first1) {
9
            ++first2;
10
        } else {
11
            *result = *first1;
12
            ++result;
13
            ++first1;
14
            ++first2;
15
        }
16
    }
17
    return result;
18
}

六、完整 C++ 工业级工程实现#

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
class ArrayIntersectionSolution {
6
public:
7
    // 方案一：标准双指针求交集 (保留重复出现的多重频次)
8
    static std::vector<int> intersectTwoPointers(const std::vector<int>& nums1, const std::vector<int>& nums2) {
9
        std::vector<int> result;
10
        size_t i = 0, j = 0;
11
        const size_t m = nums1.size(), n = nums2.size();
12

13
        while (i < m && j < n) {
14
            if (nums1[i] == nums2[j]) {
15
                result.push_back(nums1[i]);
16
                ++i;
17
                ++j;
18
            } else if (nums1[i] < nums2[j]) {
19
                ++i;
20
            } else {
21
                ++j;
22
            }
23
        }
24
        return result;
25
    }
26

27
    // 方案二：极不平衡数据 (nums1 极小, nums2 极大) -> 二分查找优化
28
    static std::vector<int> intersectBinarySearch(const std::vector<int>& small, const std::vector<int>& large) {
29
        std::vector<int> result;
30
        auto it_start = large.begin();
31

32
        for (int val : small) {
33
            // 在大数组剩余区间中二分查找大于等于 val 的第一个位置
34
            auto it = std::lower_bound(it_start, large.end(), val);
35
            if (it != large.end() && *it == val) {
36
                result.push_back(val);
37
                it_start = it + 1; // 避免重复匹配同一位置
38
            } else {
39
                it_start = it; // 缩小下一轮二分查找的起点区间
40
            }
41
            if (it_start == large.end()) break;
42
        }
43
        return result;
44
    }
45
};
46

47
int main() {
48
    std::vector<int> A = {1, 3, 4, 7, 9, 11};
49
    std::vector<int> B = {2, 3, 5, 7, 8, 9, 12};
50

51
    auto res = ArrayIntersectionSolution::intersectTwoPointers(A, B);
52
    std::cout << "Intersection: ";
53
    for (int num : res) {
54
        std::cout << num << " ";
55
    }
56
    std::cout << std::endl; // 输出: 3 7 9
57
    return 0;
58
}

🎯 总结与面试应答速记卡#

1
                  ┌──────────────────────────────────────────────┐
2
                  │ 递增有序数组寻找相同数值 (求交集)            │
3
                  └──────────────────────┬───────────────────────┘
4
                                         │
5
                 ┌───────────────────────┴───────────────────────┐
6
                 ▼                                               ▼
7
     【常规规模 M ≈ N】                               【极端不均衡 M ≪ N】
8
     双指针同向扫描                                   遍历短数组 A + 在长数组 B 中二分
9
     时间: O(M + N)                                   时间: O(M log N)
10
     空间: O(1)                                       空间: O(1)
11
                 │                                               │
12
                 └───────────────────────┬───────────────────────┘
13
                                         ▼
14
                             【超内存限制 / 磁盘海量数据】
15
                             分块流式归并 (Block Streaming Merge)
16
                             内存严格 O(1)，全顺序磁盘 I/O

Kuchina 's Blog

秋招算法高频精讲：双指针与有序数组求交集深度复盘（含极端数据与工程追问）#

Author#

📌 真实面试背景#

目录#

一、算法一：标准双指针扫描法（Baseline）#

1. 核心数学原理#

2. 复杂度分析#

二、算法二：极不平衡规模优化——二分查找法（ $M \ll N$ ）#

1. 痛点：为什么双指针不是万能的？#

2. 复杂度#

三、算法三：指数跳跃搜索（Galloping / Exponential Search）#

四、算法四：海量数据与外排序流式处理（Memory Constraint）#

1. 极端场景：数组数据无法一次性放入内存#

2. 流式归并方案（Block-based Streaming Merge）#

五、重复元素处理策略与 STL 源码对比#

1. 去重（Unique Elements Only） vs 保留多重频次（Multi-set Intersection）#

2. C++ STL `std::set_intersection` 源码核心剖析#

六、完整 C++ 工业级工程实现#

🎯 总结与面试应答速记卡#

Continue reading

Take another route

Comments

Kuchina 's Blog

秋招算法高频精讲：双指针与有序数组求交集深度复盘（含极端数据与工程追问）#

Author#

📌 真实面试背景#

目录#

一、 算法一：标准双指针扫描法（Baseline）#

1. 核心数学原理#

2. 复杂度分析#

二、 算法二：极不平衡规模优化——二分查找法（M≪NM \ll NM≪N）#

1. 痛点：为什么双指针不是万能的？#

2. 复杂度#

三、 算法三：指数跳跃搜索（Galloping / Exponential Search）#

四、 算法四：海量数据与外排序流式处理（Memory Constraint）#

1. 极端场景：数组数据无法一次性放入内存#

2. 流式归并方案（Block-based Streaming Merge）#

五、 重复元素处理策略与 STL 源码对比#

1. 去重（Unique Elements Only） vs 保留多重频次（Multi-set Intersection）#

2. C++ STL std::set_intersection 源码核心剖析#

六、 完整 C++ 工业级工程实现#

🎯 总结与面试应答速记卡#

Share Article

Related reading

Take another route

Comments

一、算法一：标准双指针扫描法（Baseline）#

二、算法二：极不平衡规模优化——二分查找法（ $M \ll N$ ）#

三、算法三：指数跳跃搜索（Galloping / Exponential Search）#

四、算法四：海量数据与外排序流式处理（Memory Constraint）#

五、重复元素处理策略与 STL 源码对比#

2. C++ STL `std::set_intersection` 源码核心剖析#

六、完整 C++ 工业级工程实现#