1. 题目背景与核心需求这道来自蚂蚁集团2026年春招的编程题考察的是对二元组数据的处理能力。题目描述如下给定两个整数数组nums1和nums2统计满足以下条件的二元组(i,j)的数量nums1[i] nums2[j]i j这类问题在实际开发中非常常见比如在电商系统中匹配用户行为日志、在推荐系统中对齐用户画像特征等。理解这类问题的解法对处理真实业务中的数据集对齐场景很有帮助。2. 暴力解法与复杂度分析最直观的解法是双层循环遍历def count_pairs(nums1, nums2): count 0 for i in range(len(nums1)): for j in range(len(nums2)): if nums1[i] nums2[j] and i j: count 1 return count时间复杂度O(n²)空间复杂度O(1)虽然这种解法在小数据量时可行但在面试中显然不够理想。蚂蚁的面试题通常期望候选人能给出更优解。3. 哈希表优化解法我们可以利用哈希表来优化时间复杂度from collections import defaultdict def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: # 找到nums2中所有等于nums1[i]且位置大于i的j for j in num_map[num]: if i j: count 1 return count时间复杂度O(nm)其中n和m分别是两个数组的长度空间复杂度O(m)用于存储nums2的索引4. 进一步优化二分查找当nums2中存在大量重复元素时可以进一步优化import bisect def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: # 使用二分查找找到第一个大于i的位置 indices num_map[num] pos bisect.bisect_right(indices, i) count len(indices) - pos return count时间复杂度O(n log m)空间复杂度O(m)5. 多语言实现对比5.1 Java实现import java.util.*; public class Solution { public int countPairs(int[] nums1, int[] nums2) { MapInteger, ListInteger numMap new HashMap(); for (int j 0; j nums2.length; j) { numMap.computeIfAbsent(nums2[j], k - new ArrayList()).add(j); } int count 0; for (int i 0; i nums1.length; i) { if (numMap.containsKey(nums1[i])) { ListInteger indices numMap.get(nums1[i]); int pos Collections.binarySearch(indices, i); if (pos 0) pos -pos - 1; count indices.size() - pos; } } return count; } }5.2 C实现#include vector #include unordered_map #include algorithm using namespace std; int countPairs(vectorint nums1, vectorint nums2) { unordered_mapint, vectorint numMap; for (int j 0; j nums2.size(); j) { numMap[nums2[j]].push_back(j); } int count 0; for (int i 0; i nums1.size(); i) { if (numMap.find(nums1[i]) ! numMap.end()) { auto indices numMap[nums1[i]]; auto it upper_bound(indices.begin(), indices.end(), i); count distance(it, indices.end()); } } return count; }5.3 Python实现最终优化版from collections import defaultdict import bisect def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: indices num_map[num] pos bisect.bisect_right(indices, i) count len(indices) - pos return count6. 测试用例设计全面的测试用例应该包括test_cases [ # 基础测试 ([1,2,3], [1,2,3], 3), ([1,1,1], [1,1,1], 6), # 边界测试 ([], [], 0), ([1], [2], 0), # 特殊测试 ([1,2,3], [3,2,1], 1), ([1,2,2], [2,2,2], 4), # 大数据测试 (list(range(10000)), list(range(10000)), 49995000) ] for nums1, nums2, expected in test_cases: assert count_pairs(nums1, nums2) expected7. 性能优化思考在实际业务场景中还可以考虑以下优化方向如果数组已经排序可以使用双指针法进一步优化对于特别大的数据集可以考虑分块处理或使用布隆过滤器在多线程环境下可以将哈希表的构建和查询过程并行化8. 常见面试问题面试官可能会追问如何处理数据量特别大的情况如果nums2不能全部放入内存怎么办如何将这个算法扩展到分布式环境9. 实际业务应用这类算法在以下场景中有广泛应用用户行为分析匹配不同时间段的用户行为推荐系统对齐用户和物品的特征数据清洗找出不同数据源中的匹配项10. 编码规范建议在面试中写代码时要注意先明确输入输出和边界条件写注释说明算法思路变量命名要有意义处理可能的异常情况11. 复杂度分析进阶对于更复杂的情况可以考虑预处理时间复杂度查询时间复杂度空间复杂度的权衡数据分布对算法性能的影响12. 算法选择策略选择算法时需要考虑数据规模数据分布特征内存限制是否需要支持动态更新13. 在线测试技巧在在线编程平台测试时先通过所有示例测试用例添加自己的边界测试测试大数据量下的表现检查内存使用情况14. 面试评分标准这类题目通常会考察基础编码能力算法优化思路代码规范性问题分析能力沟通表达能力15. 学习资源推荐想深入掌握这类问题可以学习《算法导论》中的哈希表相关章节LeetCode上的Two Sum系列题目系统设计中的数据处理模式分布式算法中的数据分片技术16. 个人实战建议根据我的面试经验先写出暴力解法再逐步优化主动分析时间/空间复杂度讨论可能的优化方向考虑实际业务中的约束条件保持代码整洁和可读性 
长河君 · 2026/11/4 21:06:30 · 阅读 1.2k 哈希表与二分查找优化二元组统计问题
1. 题目背景与核心需求这道来自蚂蚁集团2026年春招的编程题考察的是对二元组数据的处理能力。题目描述如下给定两个整数数组nums1和nums2统计满足以下条件的二元组(i,j)的数量nums1[i] nums2[j]i j这类问题在实际开发中非常常见比如在电商系统中匹配用户行为日志、在推荐系统中对齐用户画像特征等。理解这类问题的解法对处理真实业务中的数据集对齐场景很有帮助。2. 暴力解法与复杂度分析最直观的解法是双层循环遍历def count_pairs(nums1, nums2): count 0 for i in range(len(nums1)): for j in range(len(nums2)): if nums1[i] nums2[j] and i j: count 1 return count时间复杂度O(n²)空间复杂度O(1)虽然这种解法在小数据量时可行但在面试中显然不够理想。蚂蚁的面试题通常期望候选人能给出更优解。3. 哈希表优化解法我们可以利用哈希表来优化时间复杂度from collections import defaultdict def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: # 找到nums2中所有等于nums1[i]且位置大于i的j for j in num_map[num]: if i j: count 1 return count时间复杂度O(nm)其中n和m分别是两个数组的长度空间复杂度O(m)用于存储nums2的索引4. 进一步优化二分查找当nums2中存在大量重复元素时可以进一步优化import bisect def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: # 使用二分查找找到第一个大于i的位置 indices num_map[num] pos bisect.bisect_right(indices, i) count len(indices) - pos return count时间复杂度O(n log m)空间复杂度O(m)5. 多语言实现对比5.1 Java实现import java.util.*; public class Solution { public int countPairs(int[] nums1, int[] nums2) { MapInteger, ListInteger numMap new HashMap(); for (int j 0; j nums2.length; j) { numMap.computeIfAbsent(nums2[j], k - new ArrayList()).add(j); } int count 0; for (int i 0; i nums1.length; i) { if (numMap.containsKey(nums1[i])) { ListInteger indices numMap.get(nums1[i]); int pos Collections.binarySearch(indices, i); if (pos 0) pos -pos - 1; count indices.size() - pos; } } return count; } }5.2 C实现#include vector #include unordered_map #include algorithm using namespace std; int countPairs(vectorint nums1, vectorint nums2) { unordered_mapint, vectorint numMap; for (int j 0; j nums2.size(); j) { numMap[nums2[j]].push_back(j); } int count 0; for (int i 0; i nums1.size(); i) { if (numMap.find(nums1[i]) ! numMap.end()) { auto indices numMap[nums1[i]]; auto it upper_bound(indices.begin(), indices.end(), i); count distance(it, indices.end()); } } return count; }5.3 Python实现最终优化版from collections import defaultdict import bisect def count_pairs(nums1, nums2): num_map defaultdict(list) for idx, num in enumerate(nums2): num_map[num].append(idx) count 0 for i, num in enumerate(nums1): if num in num_map: indices num_map[num] pos bisect.bisect_right(indices, i) count len(indices) - pos return count6. 测试用例设计全面的测试用例应该包括test_cases [ # 基础测试 ([1,2,3], [1,2,3], 3), ([1,1,1], [1,1,1], 6), # 边界测试 ([], [], 0), ([1], [2], 0), # 特殊测试 ([1,2,3], [3,2,1], 1), ([1,2,2], [2,2,2], 4), # 大数据测试 (list(range(10000)), list(range(10000)), 49995000) ] for nums1, nums2, expected in test_cases: assert count_pairs(nums1, nums2) expected7. 性能优化思考在实际业务场景中还可以考虑以下优化方向如果数组已经排序可以使用双指针法进一步优化对于特别大的数据集可以考虑分块处理或使用布隆过滤器在多线程环境下可以将哈希表的构建和查询过程并行化8. 常见面试问题面试官可能会追问如何处理数据量特别大的情况如果nums2不能全部放入内存怎么办如何将这个算法扩展到分布式环境9. 实际业务应用这类算法在以下场景中有广泛应用用户行为分析匹配不同时间段的用户行为推荐系统对齐用户和物品的特征数据清洗找出不同数据源中的匹配项10. 编码规范建议在面试中写代码时要注意先明确输入输出和边界条件写注释说明算法思路变量命名要有意义处理可能的异常情况11. 复杂度分析进阶对于更复杂的情况可以考虑预处理时间复杂度查询时间复杂度空间复杂度的权衡数据分布对算法性能的影响12. 算法选择策略选择算法时需要考虑数据规模数据分布特征内存限制是否需要支持动态更新13. 在线测试技巧在在线编程平台测试时先通过所有示例测试用例添加自己的边界测试测试大数据量下的表现检查内存使用情况14. 面试评分标准这类题目通常会考察基础编码能力算法优化思路代码规范性问题分析能力沟通表达能力15. 学习资源推荐想深入掌握这类问题可以学习《算法导论》中的哈希表相关章节LeetCode上的Two Sum系列题目系统设计中的数据处理模式分布式算法中的数据分片技术16. 个人实战建议根据我的面试经验先写出暴力解法再逐步优化主动分析时间/空间复杂度讨论可能的优化方向考虑实际业务中的约束条件保持代码整洁和可读性