本文详解使用双指针法在两个升序数组中线性时间查找重复元素的正确实现，对比二分搜索等替代方案的复杂度，并提供可运行代码与性能分析。
本文详解使用双指针法在两个升序数组中线性时间查找重复元素的正确实现，对比二分搜索等替代方案的复杂度，并提供可运行代码与性能分析。
在处理已排序数组时，利用其有序性是优化算法的关键。您提供的 findDuplicatesFinalVersion 方法正是经典的双指针归并式遍历法，它完全符合题目要求——在两个不含内部重复元素的升序数组中，统计公共元素（即“重复”出现在两数组中的值）的数量。
该实现逻辑严谨、时间复杂度最优：
- 使用两个指针
index1和index2分别遍历arr1和arr2； - 当
arr1[index1] 时，说明arr1当前元素过小，无法匹配，故index1++； - 当相等时，确认一个公共元素，
count++，且两指针同步前移（因数组自身无重复，无需重复匹配）； - 当
arr1[index1] > arr2[index2]时，index2++。
✅ 正确性验证示例：
int[] a = {1, 3, 5, 7, 9};
int[] b = {3, 4, 5, 8, 9, 10};
System.out.println(findDuplicatesFinalVersion(a, b)); // 输出：3（对应 3, 5, 9）
⏱️ 时间复杂度分析：
- 双指针法：O(m + n)，每个元素最多被访问一次，是理论最优解；
- 替代方案（如对较小数组遍历 + 在较大数组中二分查找）：O(min(m,n) × log(max(m,n)))。
当两数组规模接近时（如 m ≈ n），O(m+n) 显著优于 O(n log n)；即使规模差异大（如 n=1000, m=10⁶），O(1000×log₂10⁶≈20,000) 与 O(1,001,000) 相比看似占优，但实际常数开销（函数调用、分支预测失败、缓存不友好）往往使二分法在中等数据量下反而更慢。Stack Overflow 的经典讨论 [O(n log m) vs O(n+m)] 明确指出：除非 m 极大而 n 极小（如 n=10, m=2¹⁰⁰），否则双指针法在实践中更高效且更简洁。
⚠️ 注意事项：
- 该算法严格依赖输入数组已升序排列且各自无重复。若前提不满足，结果不可靠；
- 若需返回具体重复元素（而非仅计数），可将
count++替换为list.add(arr1[index1])； - 边界安全：循环条件
index1 已完备，无需额外空数组检查（但生产环境建议增加Objects.requireNonNull防御性校验）。
✅ 总结：您的实现不仅是“正确的”，更是该问题场景下的标准最优解。它简洁、高效、易理解，完美契合题目对“sorted arrays + no internal duplicates + count duplicates”这一约束条件的设计目标。无需过度优化——真正的工程智慧，往往在于选择最匹配问题本质的简单解法。
