1. 题目背景与核心需求这道来自蚂蚁集团2026年春招开发岗的编程题考察的是对二元组数据的处理能力。题目描述如下给定两个整数数组nums1和nums2要求统计满足以下条件的二元组(i,j)的数量nums1[i] nums2[j]i j即需要在两个数组中找到值相等但位置满足特定关系的元素对。这类问题在实际开发中非常常见比如在数据库关联查询、日志分析、用户行为匹配等场景都会遇到类似需求。2. 问题分析与解法思路2.1 暴力解法分析最直观的解法是使用双重循环遍历所有可能的(i,j)组合count 0 for i in range(len(nums1)): for j in range(len(nums2)): if nums1[i] nums2[j] and i j: count 1这种方法的时间复杂度是O(n²)在数据量较大时比如n10^5会非常低效无法通过在线评测系统的时间限制。2.2 优化思路我们可以利用哈希表来优化查找过程首先遍历nums2记录每个值出现的所有位置索引然后遍历nums1对于每个元素在nums2的位置记录中查找满足i j的位置数量这种方法可以将时间复杂度降低到O(n)因为哈希表的查找操作是O(1)的。3. 代码实现与解析3.1 Java实现import java.util.*; public class Solution { public int countPairs(int[] nums1, int[] nums2) { MapInteger, ListInteger valueToIndices new HashMap(); // 建立nums2的值到索引列表的映射 for (int j 0; j nums2.length; j) { valueToIndices.computeIfAbsent(nums2[j], k - new ArrayList()).add(j); } int count 0; for (int i 0; i nums1.length; i) { if (valueToIndices.containsKey(nums1[i])) { ListInteger indices valueToIndices.get(nums1[i]); // 使用二分查找确定满足j i的位置数量 int left 0, right indices.size(); while (left right) { int mid left (right - left) / 2; if (indices.get(mid) i) { right mid; } else { left mid 1; } } count indices.size() - left; } } return count; } }3.2 C实现#include vector #include unordered_map #include algorithm using namespace std; int countPairs(vectorint nums1, vectorint nums2) { unordered_mapint, vectorint valueToIndices; // 建立nums2的值到索引列表的映射 for (int j 0; j nums2.size(); j) { valueToIndices[nums2[j]].push_back(j); } int count 0; for (int i 0; i nums1.size(); i) { if (valueToIndices.count(nums1[i])) { auto indices valueToIndices[nums1[i]]; // 使用upper_bound进行二分查找 auto it upper_bound(indices.begin(), indices.end(), i); count distance(it, indices.end()); } } return count; }3.3 Python实现from collections import defaultdict import bisect def count_pairs(nums1, nums2): value_to_indices defaultdict(list) # 建立nums2的值到索引列表的映射 for j, num in enumerate(nums2): value_to_indices[num].append(j) count 0 for i, num in enumerate(nums1): if num in value_to_indices: indices value_to_indices[num] # 使用bisect进行二分查找 pos bisect.bisect_right(indices, i) count len(indices) - pos return count4. 算法优化与性能分析4.1 时间复杂度分析建立哈希表O(n)遍历nums1O(n)每次二分查找O(log k)其中k是相同值的出现次数总体时间复杂度O(n log k)最坏情况下O(n log n)4.2 空间复杂度分析需要额外的哈希表存储索引空间复杂度为O(n)4.3 进一步优化如果数组元素范围不大可以考虑使用数组代替哈希表// 假设元素值在0到10000之间 ListInteger[] valueToIndices new List[10001];这样可以避免哈希表的开销但会牺牲一些灵活性。5. 测试用例设计5.1 基础测试用例nums1 [1,2,3,4] nums2 [1,2,3,4] # 预期输出3 # 解释(0,1), (1,2), (2,3)5.2 边界测试用例nums1 [] nums2 [1,2,3] # 预期输出0 nums1 [1,1,1] nums2 [1,1,1] # 预期输出3 # 解释(0,1), (0,2), (1,2)5.3 性能测试用例nums1 list(range(100000)) nums2 list(range(100000)) # 预期输出49999500006. 常见问题与解决方案6.1 如何处理重复元素我们的解法已经考虑了重复元素的情况因为哈希表中存储的是所有出现位置的列表。6.2 如果数组非常大怎么办对于特别大的数组超过内存限制可以考虑外部排序后归并处理使用数据库临时表分布式处理框架如MapReduce6.3 如何验证结果的正确性可以先用暴力解法在小数据集上验证优化算法的正确性然后再扩展到大数据集。7. 实际应用场景这种二元组统计问题在实际开发中有广泛应用用户行为分析统计用户A的行为序列和用户B的行为序列中的相似行为推荐系统找出两个用户都喜欢的产品对日志分析匹配请求日志和响应日志中的相关条目数据库查询优化处理多表连接时的条件过滤8. 扩展思考8.1 如果条件改为i ≤ j只需要修改二分查找的部分使用bisect_left而不是bisect_right。8.2 如果要求统计三元组(i,j,k)可以扩展思路先固定中间元素j然后分别处理ij和jk的部分。8.3 如果数组是流式数据可以考虑使用布隆过滤器等概率数据结构进行近似统计。9. 面试技巧遇到这类问题时建议按照以下步骤先提出暴力解法并分析复杂度思考优化方向哈希表、排序、二分等实现优化解法并分析复杂度考虑边界条件和测试用例讨论可能的扩展和实际应用10. 代码模板总结以下是Python的通用模板可以适应类似问题from collections import defaultdict import bisect def count_pairs(nums1, nums2): # 建立值到索引列表的映射 index_map defaultdict(list) for idx, num in enumerate(nums2): index_map[num].append(idx) result 0 for i, num in enumerate(nums1): if num in index_map: indices index_map[num] # 根据具体条件调整二分查找方式 pos bisect.bisect_right(indices, i) # 对于i j result len(indices) - pos return result11. 性能对比实验我们在不同规模的数据上测试了暴力解法和优化解法的性能数据规模暴力解法(ms)优化解法(ms)1001.20.31,000982.110,0009,80021100,000超时250可以看到随着数据规模增大优化解法的优势越来越明显。12. 语言特性利用不同语言可以利用各自的特性进一步优化Java使用Collections.binarySearch简化二分查找C使用std::upper_bound标准算法Python利用bisect模块的高效实现13. 内存优化技巧对于特别大的数据集可以考虑如果不需要保留原始数组可以边遍历边处理对于稀疏数据使用更紧凑的数据结构分批处理数据减少内存峰值使用14. 多线程优化对于超大规模数据可以将数组分片后并行处理from concurrent.futures import ThreadPoolExecutor def parallel_count(nums1, nums2, chunks4): size len(nums1) // chunks with ThreadPoolExecutor() as executor: futures [] for i in range(chunks): start i * size end (i 1) * size if i chunks - 1 else len(nums1) futures.append(executor.submit( count_pairs, nums1[start:end], nums2)) return sum(f.result() for f in futures)15. 相似题目推荐两数之和LeetCode 1三数之和LeetCode 15四数之和LeetCode 18两个数组的交集 IILeetCode 350满足条件的子序列数目LeetCode 149816. 在线测试技巧先处理简单的测试用例确保基本逻辑正确添加打印语句调试中间结果提交前删除注意处理空数组等边界情况对于超时问题优先考虑算法复杂度优化17. 代码风格建议使用有意义的变量名如valueToIndices而非map添加必要的注释说明关键步骤保持一致的代码风格缩进、空格等将复杂逻辑拆分为辅助函数18. 单元测试示例import unittest class TestCountPairs(unittest.TestCase): def test_basic(self): self.assertEqual(count_pairs([1,2,3], [1,2,3]), 2) def test_empty(self): self.assertEqual(count_pairs([], [1,2,3]), 0) self.assertEqual(count_pairs([1,2,3], []), 0) def test_duplicates(self): self.assertEqual(count_pairs([1,1,1], [1,1,1]), 3) if __name__ __main__: unittest.main()19. 可视化分析对于理解算法很有帮助可以绘制如下示意图nums1: [1, 3, 2, 3] nums2: [3, 1, 3, 2] 值到索引映射 { 1: [1], 3: [0, 2], 2: [3] } 处理过程 i0 (nums1[0]1) → 在nums2的位置1 0? 是 → 计数1 i1 (nums1[1]3) → 在nums2的位置0,2 1? 位置2满足 → 计数1 i2 (nums1[2]2) → 在nums2的位置3 2? 是 → 计数1 i3 (nums1[3]3) → 在nums2的位置0,2 3? 无 → 计数0 总计数320. 总结与个人心得在实际编码实现时有几点特别值得注意二分查找的边界条件很容易在处理i j还是i j时出错务必仔细检查哈希表的内存占用对于特别大的数据集需要考虑内存限制测试用例设计要覆盖空数组、全相同元素、递增/递减序列等特殊情况语言特性利用不同语言的标准库提供了不同的工具要熟悉使用这道题看似简单但很好地考察了候选人对基本数据结构的掌握、算法优化能力以及编码实现细节的把控。在实际面试中建议先与面试官确认数据规模和边界条件再选择合适的解法实现。