读完本文你将了解Two Sum 的核心解法 | AI 解题思路的演进 | 面试优化方向 先问一个问题猜猜 ChatGPT 第一次写这题会怎么写不是哈希表不是双指针。大概率是一个双重循环。这不是 AI 笨是最直观的人类思维“拿第一个数跟后面的每个数加一遍看看。” 第一版AI 的朴素解法暴力解deftwo_sum(nums,target):foriinrange(len(nums)):forjinrange(i1,len(nums)):ifnums[i]nums[j]target:return[i,j]return[]这版代码就是问题的直译——“找两个数让它们的和等于目标值”。人也是先试第一个和第二个不行再试第一个和第三个。时间复杂度O(n²)最坏要检查 n(n-1)/2 个组合空间复杂度O(1)只用了几个变量但面试官看到这个会在心里扣分。n 最大 10⁴O(n²) 在最坏情况下要跑 5000 万次加法。 AI 的自我优化优化的突破口在哪把找变成查。核心洞察对于每个 nums[i]不需要遍历后面所有数而是问——target - nums[i] 之前出现过吗暴力解nums[i] nums[j] targetO(n²)关键洞察target - nums[i] 出现过吗哈希表优化用 seen 字典记录已遍历的值最终版本边遍历边查O(n) 空间换时间AI 的优化版deftwo_sum(nums,target):seen{}fori,numinenumerate(nums):complementtarget-numifcomplementinseen:return[seen[complement],i]seen[num]ireturn[]改了什么暴力→哈希表时间从 O(n²) 降到 O(n)。空间升到 O(n)但值得——空间换时间是算法优化最经典的套路不需要先建表再查边遍历边查一次循环搞定时间复杂度O(n)空间复杂度O(n)结果seen 字典循环结果seen 字典循环complement9-277不在seen中complement9-722在seen中!num2, seen{}存入 {2:0}num7, seen{2:0}返回 [seen[2], 1] [0, 1]整个过程就像派对上找人不是逮着每个人问你是不是我要找的人暴力解而是进门时登记名字等你要找的人来了直接喊他哈希表。 算法模式拆解模式Hash Map哈希表/字典核心当需要快速判断一个元素是否出现过时用字典记录已遍历的元素。特征说明识别标志题目中出现和等于目标值、“差等于目标值”、“出现次数”核心操作存记录已访问元素 查判断补数是否存在复杂度特征O(n) 时间O(n) 空间——空间换时间变体Set不需要索引、Counter需要计数所有两数之和类问题的本质都是配对。一个数需要找到它的另一半。哈希表能 O(1) 回答这个另一半出现过吗这就是降维打击。️ 真实产品场景Instagram 的「共同点赞」功能帖子底下显示John 和 3 位好友已赞过——这个功能背后的逻辑和 Two Sum 一样。给定点赞用户 ID 数组找两个用户 ID 之和等于目标值的组合比如 780他们大概率在同一类内容上互动。更实际的是内容推荐系统用户 A 点赞了 P1、P2、P3用户 B 点赞了 P2、P3、P4。找点赞交集就是 Hash Map 的典型应用——先把 A 的帖子 ID 存字典遍历 B 的帖子时直接查。defmutual_likes(user_a_posts,user_b_posts):seen{}forpost_idinuser_a_posts:seen[post_id]Truemutual[]forpost_idinuser_b_posts:ifpost_idinseen:mutual.append(post_id)returnmutualInstagram 的社交推荐和 Feeds 流排序底层都有这个逻辑的影子。✅ 面试官的点评通过线写出暴力解 说出复杂度 → 60 分主动优化到哈希表 → 80 分说出为什么不用双指针因为数组无序→ 90 分加分项主动处理空数组、长度为 1 的数组先说可以用哈希表优化再写代码——先想后写提到如果空间受限可以排序后双指针但 O(n log n) 比 O(n) 慢常见踩坑点❌ 忘记检查不能重复使用同一个元素——把seen[nums[i]] i放判断前同一个元素用两次❌ 以为 Python 的in对字典不是 O(1)❌ 不问就说数组已排序 同类题推荐题目难度一句话思路167. Two Sum II - Input Array Is SortedEasy数组已排序双指针 O(n) O(1)15. 3SumMedium固定一个数剩下两个用双指针1. Two SumEasy哈希表你已掌握来源说明✅ 已验证LeetCode 官方题解 AI 实测 文档/论文算法教材引用
让 ChatGPT 写两数之和，第一版居然是 O(n²)——从暴力到最优的进化之路
读完本文你将了解Two Sum 的核心解法 | AI 解题思路的演进 | 面试优化方向 先问一个问题猜猜 ChatGPT 第一次写这题会怎么写不是哈希表不是双指针。大概率是一个双重循环。这不是 AI 笨是最直观的人类思维“拿第一个数跟后面的每个数加一遍看看。” 第一版AI 的朴素解法暴力解deftwo_sum(nums,target):foriinrange(len(nums)):forjinrange(i1,len(nums)):ifnums[i]nums[j]target:return[i,j]return[]这版代码就是问题的直译——“找两个数让它们的和等于目标值”。人也是先试第一个和第二个不行再试第一个和第三个。时间复杂度O(n²)最坏要检查 n(n-1)/2 个组合空间复杂度O(1)只用了几个变量但面试官看到这个会在心里扣分。n 最大 10⁴O(n²) 在最坏情况下要跑 5000 万次加法。 AI 的自我优化优化的突破口在哪把找变成查。核心洞察对于每个 nums[i]不需要遍历后面所有数而是问——target - nums[i] 之前出现过吗暴力解nums[i] nums[j] targetO(n²)关键洞察target - nums[i] 出现过吗哈希表优化用 seen 字典记录已遍历的值最终版本边遍历边查O(n) 空间换时间AI 的优化版deftwo_sum(nums,target):seen{}fori,numinenumerate(nums):complementtarget-numifcomplementinseen:return[seen[complement],i]seen[num]ireturn[]改了什么暴力→哈希表时间从 O(n²) 降到 O(n)。空间升到 O(n)但值得——空间换时间是算法优化最经典的套路不需要先建表再查边遍历边查一次循环搞定时间复杂度O(n)空间复杂度O(n)结果seen 字典循环结果seen 字典循环complement9-277不在seen中complement9-722在seen中!num2, seen{}存入 {2:0}num7, seen{2:0}返回 [seen[2], 1] [0, 1]整个过程就像派对上找人不是逮着每个人问你是不是我要找的人暴力解而是进门时登记名字等你要找的人来了直接喊他哈希表。 算法模式拆解模式Hash Map哈希表/字典核心当需要快速判断一个元素是否出现过时用字典记录已遍历的元素。特征说明识别标志题目中出现和等于目标值、“差等于目标值”、“出现次数”核心操作存记录已访问元素 查判断补数是否存在复杂度特征O(n) 时间O(n) 空间——空间换时间变体Set不需要索引、Counter需要计数所有两数之和类问题的本质都是配对。一个数需要找到它的另一半。哈希表能 O(1) 回答这个另一半出现过吗这就是降维打击。️ 真实产品场景Instagram 的「共同点赞」功能帖子底下显示John 和 3 位好友已赞过——这个功能背后的逻辑和 Two Sum 一样。给定点赞用户 ID 数组找两个用户 ID 之和等于目标值的组合比如 780他们大概率在同一类内容上互动。更实际的是内容推荐系统用户 A 点赞了 P1、P2、P3用户 B 点赞了 P2、P3、P4。找点赞交集就是 Hash Map 的典型应用——先把 A 的帖子 ID 存字典遍历 B 的帖子时直接查。defmutual_likes(user_a_posts,user_b_posts):seen{}forpost_idinuser_a_posts:seen[post_id]Truemutual[]forpost_idinuser_b_posts:ifpost_idinseen:mutual.append(post_id)returnmutualInstagram 的社交推荐和 Feeds 流排序底层都有这个逻辑的影子。✅ 面试官的点评通过线写出暴力解 说出复杂度 → 60 分主动优化到哈希表 → 80 分说出为什么不用双指针因为数组无序→ 90 分加分项主动处理空数组、长度为 1 的数组先说可以用哈希表优化再写代码——先想后写提到如果空间受限可以排序后双指针但 O(n log n) 比 O(n) 慢常见踩坑点❌ 忘记检查不能重复使用同一个元素——把seen[nums[i]] i放判断前同一个元素用两次❌ 以为 Python 的in对字典不是 O(1)❌ 不问就说数组已排序 同类题推荐题目难度一句话思路167. Two Sum II - Input Array Is SortedEasy数组已排序双指针 O(n) O(1)15. 3SumMedium固定一个数剩下两个用双指针1. Two SumEasy哈希表你已掌握来源说明✅ 已验证LeetCode 官方题解 AI 实测 文档/论文算法教材引用
