读完本文你将了解Two Sum 的 4 轮优化路径 | AI 为什么会走排序双指针的死胡同 | Instagram 真实场景下的哈希表实战 题目原题给定一个整数数组nums和一个目标值target返回数组中和为target的两个元素的下标。你可以假设每种输入只会对应一个答案不能重复使用数组中的同一元素。项目说明输入nums [2, 7, 11, 15], target 9输出[0, 1]约束2 ≤ nums.length ≤ 10⁴仅有一个有效答案不能重复使用同一元素 先问一个问题如果让你用一句话描述这道题你会说什么“找两个数加起来等于目标值”——对但 AI 第一次写的时候想的不是找两个数而是找一对索引。这微小的差别决定了它第一版解法的方向。让 ChatGPT 第一次写这道题它会给出什么 第一版AI 的朴素解法让 AI 写它几乎必写暴力法。原因不是笨是因为这是人类直觉的映射——“找两个数” → “两两配对” → 双重循环。deftwo_sum(nums:list[int],target:int)-list[int]:nlen(nums)foriinrange(n):forjinrange(i1,n):ifnums[i]nums[j]target:return[i,j]return[]时间复杂度 O(n²)空间 O(1)。当 n 10⁴ 时最坏要跑 5000 万次加法——慢但对 90% 的面试者来说这版已经能过 Easy。 AI 的 4 轮优化AI 的优化路径不是线性的。它不会直接跳到哈希表而是走一条先排序后反悔的弯路。第 1 次优化排序 二分查找AI 的逻辑是先排序对每个元素用二分查找找target - nums[i]。deftwo_sum_v2(nums:list[int],target:int)-list[int]:indexedsorted(enumerate(nums),keylambdax:x[1])fori,(orig_i,val)inenumerate(indexed):low,highi1,len(indexed)-1whilelowhigh:mid(lowhigh)//2ifindexed[mid][1]target-val:return[orig_i,indexed[mid][0]]elifindexed[mid][1]target-val:lowmid1else:highmid-1return[]时间 O(n log n)空间 O(n)。但这里有个大坑原数组没排序排完序后索引全乱了必须用enumerate记录原始位置代码量直接翻倍。面试官会问一句为什么要记原始索引——如果你答不上来这版反而扣分。第 2 次优化排序 双指针AI 意识到二分太绕转而用双指针从两端向中间逼近。deftwo_sum_v3(nums:list[int],target:int)-list[int]:indexedsorted(enumerate(nums),keylambdax:x[1])left,right0,len(indexed)-1whileleftright:totalindexed[left][1]indexed[right][1]iftotaltarget:return[indexed[left][0],indexed[right][0]]eliftotaltarget:left1else:right-1return[]时间 O(n log n)空间 O(n)。比二分少了一层循环嵌套但仍然要保存原始索引——这是排序系方案的通病。第 3 次优化反悔了用哈希表到这一步AI 会意识到排序是多余的。真正的问题不是找两个数而是对每个数它的搭档在哪里。deftwo_sum_v4(nums:list[int],target:int)-list[int]:seen{}fori,numinenumerate(nums):complementtarget-numifcomplementinseen:return[seen[complement],i]seen[num]ireturn[]时间 O(n)空间 O(n)。一次遍历无需排序天然保留索引。这才是最优解。暴力解O(n²)排序二分O(n log n)排序双指针O(n log n)哈希表一次遍历O(n)返回结果哈希表 seentarget - nums[i]nums[i]返回结果哈希表 seentarget - nums[i]nums[i]第 1 轮i0, nums[0]2第 2 轮i1, nums[1]7complement 9-2 7查 7 在不在不在seen {2:0}complement 9-7 2查 2 在不在在return [seen[2], 1] [0, 1]☕ Java 实现publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegerseennewHashMap();for(inti0;inums.length;i){intcomplementtarget-nums[i];if(seen.containsKey(complement)){returnnewint[]{seen.get(complement),i};}seen.put(nums[i],i);}returnnewint[0];}CSDN 上 Java 读者占大头这版思路完全一致HashMap 代替 dict逐行可对照理解。 这道题到底属于哪个模式不是滑动窗口不是双指针是哈希表。很多文章把 Two Sum 归到双指针模式这不准确。双指针的核心前提是数据有序而原题没要求排序。哈希表的本质是O(1) 的反向查找。我们遍历到 nums[i] 时需要的信息是target - nums[i] 之前有没有出现过出现过在哪里——这是一个反向查询问题哈希表天然擅长。️ 真实产品场景Instagram 去重点赞想象你在 Instagram 做一个功能用户点击点赞系统要判断这条帖子今天有没有被别人点赞过同时还要记录谁点赞了。如果用最朴素的方案每次点赞都要遍历所有历史点赞记录来查重——O(n²)用户多点几次就卡了。Instagram 的实际做法是哈希表或布隆过滤器 精确查询key 帖子 IDvalue 点赞用户集合set每次点赞 O(1) 查重 O(1) 插入。这和 Two Sum 的优化逻辑一模一样把遍历查找换成哈希反向查询O(n²) 直接降到 O(n)。✅ 面试官的评分标准程度说明及格暴力法 能说清 O(n²)良好哈希表 O(n)边说思路边写优秀主动对比排序双指针和哈希表的优劣解释为什么哈希表更优加分指出重复元素、负数、超大数组的处理方式 同类题推荐167. Two Sum II — Input Array Is SortedMedium数组已排序直接用双指针不需要哈希表1. 3SumMedium排序 双指针的模板题注意去重逻辑15. 3Sum ClosestMedium在 3Sum 基础上变体思路一致但找最接近来源说明✅ 已验证LeetCode 官方题解 实测4 种解法均通过 算法模板leetcode-teacher Pattern #2 Hash Map