计算两有序集合差集的最高效算法及伪代码实现

当集合A、B排序规则一致、均为已排序状态时，求差集A\B（所有属于A但不属于B的元素构成的集合）的最高效实现是双指针线性扫描法。
这个算法的时间复杂度为O(m+n)（m、n分别为A、B的元素个数），除了存储最终结果的空间外仅需常数级额外空间，全程遍历无回溯，不需要额外构建哈希表、也不需要多次二分查找的开销，是该场景下的理论最优方案。
核心逻辑非常直接：

• 初始化两个指针i、j，分别指向A、B的起始位置，初始值为0
• 同步遍历两个集合，每次比较两个指针指向的元素值：
  • 若A[i] < B[j]：因为B是升序排列，B中j位置之后的所有元素都比B[j]大，不可能出现和A[i]相等的值，因此A[i]属于差集，加入结果，i指针后移
  • 若A[i] > B[j]：B[j]比当前A[i]小，不可能和当前及之后的A元素匹配，j指针后移
  • 若A[i] == B[j]：该元素属于两个集合的交集，不属于差集，两个指针同时后移跳过该元素
• 当任意一个指针走到对应集合的末尾时停止第一轮遍历，如果此时i还没走到A的末尾，说明A剩下的所有元素都比B的最大元素大，不可能在B中存在，直接全部加入结果即可

如果待处理的序列允许重复元素，只需要在两值相等的分支里额外跳过连续的同值重复项即可；如果是严格无重复的数学集合，不需要额外处理。如果集合是降序排列，只需要把比较逻辑的大小判断反转，核心双指针思路不变。

function sortedSetDifference(A, B):
    res = 空列表
    i = 0
    j = 0
    lenA = A的元素总数
    lenB = B的元素总数

    while i < lenA 且 j < lenB:
        if A[i] < B[j]:
            res.append(A[i])
            i = i + 1
        elif A[i] > B[j]:
            j = j + 1
        else:
            // 元素相等，属于交集，直接跳过
            i = i + 1
            j = j + 1

    // 把A中剩余未遍历的元素全部加入差集
    while i < lenA:
        res.append(A[i])
        i = i + 1

    return res

补充说明：如果两个集合长度差距极大（比如A有100万元素，B只有10个元素），可以改用遍历B中元素、在A中做二分查找标记删除的方案，实际性能会更高；但在两个集合长度相近的通用场景下，双指针法的实现简单、缓存友好性最好，性能最优。

内容的提问来源于stack exchange，提问作者cinnamond