三亚市网站建设_网站建设公司_博客网站_seo优化

一、题目本质

在数组中寻找两个不同下标i ≠ j，使得
nums[i] + nums[j] = target
返回下标，不是值

关键限制：

• 只能用一次同一个元素
• 一定有且只有一个解

二、最优解法：哈希表（一次遍历）

核心思想（一句话）

一边遍历，一边用哈希表记录“我见过的数及其下标”，当前数只需要找“target − 当前值”是否已经出现过。

三、算法流程（逻辑级）

1. 初始化一个空哈希表map

2. 遍历数组nums，索引为i

3. 对当前元素x = nums[i]

   • 计算need = target - x

4. 如果need已在哈希表中

   • 直接返回[map[need], i]

5. 否则，将x: i存入哈希表

四、Python 标准实现（面试版）

deftwoSum(nums,target):hashmap={}fori,numinenumerate(nums):need=target-numifneedinhashmap:return[hashmap[need],i]hashmap[num]=i

五、为什么不能先存再查？

正确顺序（查 → 存）

ifneedinhashmap:return...hashmap[num]=i

原因

防止以下情况：

nums = [3, 3], target = 6

如果先存再查，会错误地使用同一个元素两次。

六、复杂度分析

这是该题的理论最优解。

3️⃣hashmap是字典吗？

是的。

在 Python 中：

hashmap={}# dict

语义是：

值 → 下标 nums[i] → i

二、Two Sum 的「人脑推理流程」

我们不写代码，纯用思维走一遍。

核心转化（最重要的一步）

原问题：

nums[i] + nums[j] = target

等价于：

nums[j] = target - nums[i]

这一步意味着：

当我看到一个数 x，我并不关心未来，我只关心“过去有没有 target - x”。

三、为什么一定是「边遍历边查表」？

因为我们的问题是：

当前数能不能和“之前出现过的某个数”组成答案？

所以你需要一个结构来保存：

• 之前看过的数
• 它们各自的下标

这正是hashmap的职责。

dict和list的“使用方式差异”本质上反映的是两种不同的数据模型。

一、先给你一个总对比（定型用）

list：我只管往后放
dict：我必须明确“放在哪个 key 下”

二、dict 最常用的方法（算法题必会）

下面这些是你在 LeetCode / 面试中90% 会用到的 dict 方法。

1️⃣ 插入 / 更新（最常用）

d[key]=value

示例：

hashmap={}hashmap[3]=0hashmap[5]=2

如果 key 已存在：

• value 会被覆盖

2️⃣ 判断 key 是否存在（极高频）

ifkeyind:

Two Sum 的核心：

iftarget-numinhashmap:

⚠️ 注意：

• in只检查 key
• 不检查 value

3️⃣ 读取 value（直接）

value=d[key]

⚠️ 如果 key 不存在，会抛异常KeyError

4️⃣ 安全读取（推荐）

value=d.get(key)

或带默认值：

value=d.get(key,0)

算法中常用来做计数

5️⃣ 删除元素

deld[key]

或安全删除：

d.pop(key,None)

三、dict 在算法题里的三大经典用法

这是你应该形成条件反射的三类模式。

模式一：查互补值（Two Sum）

hashmap={}fori,numinenumerate(nums):iftarget-numinhashmap:return[hashmap[target-num],i]hashmap[num]=i

📌 关键词：查 key 是否存在

模式二：计数（频率统计）

count={}forxinnums:count[x]=count.get(x,0)+1

等价于：

fromcollectionsimportCounter count=Counter(nums)

📌 关键词：get + 默认值

模式三：记录“第一次 / 最近一次出现位置”

pos={}fori,xinenumerate(nums):ifxnotinpos:pos[x]=i# 第一次出现

或：

pos[x]=i# 永远记录最近一次

四、为什么 dict 没有 append？

这是你问的本质问题。

list 的模型是：

[ 元素0 , 元素1 , 元素2 , ... ]

所以它天然支持：

lst.append(x)

dict 的模型是：

key1 → value1 key2 → value2

没有“下一个空位”这个概念
所以 Python 逼你必须明确：

d[哪个key]=什么value

一、题目本质（先定型）

字母异位词 = 字母种类相同、每个字母出现次数相同，只是顺序不同

所以核心不是字符串顺序，而是：

“组成特征”是否一致

二、这题为什么一定要用 dict？

我们要做的是：

把“特征相同的字符串”放进同一个桶里

这在算法上叫：

分类 / 分组（group by）

而dict 天然就是“key → 一组 value” 的结构。

三、整体思考逻辑（人脑版）

1. 遍历每一个字符串s

2. 抽取一个稳定的特征 key

3. 用这个 key 去 dict 里：

   • 如果 key 已存在 → 把s放进去
   • 如果 key 不存在 → 新建一个列表，再放进去

四、关键问题：key 应该是什么？

这是本题唯一的难点。

方法一（最常见）：排序后的字符串（面试首选）

"eat" → "aet" "tea" → "aet" "ate" → "aet"

排序后完全一样 ⇒ 一定是异位词

五、代码实现（标准面试版）

使用 dict + list

defgroupAnagrams(strs):groups={}forsinstrs:key=''.join(sorted(s))ifkeynotingroups:groups[key]=[]groups[key].append(s)returnlist(groups.values())

六、你现在应该注意到的 dict 用法

这题把 dict 的常见用法全部用了一遍：

1️⃣ 用 key 分类

groups[key]

2️⃣ key 不存在时，初始化一个 list

groups[key]=[]

3️⃣ list 才用 append

groups[key].append(s)

📌这点非常重要：

dict 不 append，list 才 append

七、写得更“Pythonic”的版本（理解后再用）

fromcollectionsimportdefaultdictdefgroupAnagrams(strs):groups=defaultdict(list)forsinstrs:key=''.join(sorted(s))groups[key].append(s)returnlist(groups.values())

defaultdict 干了什么？

groups[key]=[]

这一步它帮你自动做了。

八、复杂度分析（面试会问）

假设：

• n = 字符串数量
• k = 每个字符串平均长度

九、为什么不能用 list 直接做？

如果你尝试：

res=[]

你会遇到问题：

• 每来一个字符串
• 要和所有已有组逐个比
• 判断是否是异位词（又要计数 / 排序）

👉退化为 O(n²)

十、把这题和你前面的学习连起来

一句总括：

dict 的核心用途只有两个：快速查找，或者按特征分组。

1️⃣for s in strs能不能换成for i in range(len(strs))？

完全可以，逻辑等价。

foriinrange(len(strs)):s=strs[i]

和：

forsinstrs:

区别只有一个：

• 第二种更 Pythonic、更简洁
• 第一种在需要“索引 i”时才用

📌 本题不需要索引，所以直接for s in strs是最合适的。

二、最关键的问题：为什么key = ''.join(sorted(s))？

这行代码是整道题的灵魂。

先拆开来看

sorted(s)

• s是字符串，比如"eat"

• sorted(s)的结果是：

  ['a','e','t']

⚠️ 注意：返回的是 list，不是字符串

那为什么要join？

字典的 key 必须是：

• 不可变类型
• 字符串 / 数字 / tuple 都可以

但list 不能作为 key，因为它是可变的。

所以我们要把：

['a','e','t']

变成：

"aet"

这就是：

''.join(sorted(s))

📌join 的作用：

把字符列表重新拼成一个字符串，作为 dict 的 key

三、那为什么“排序后的字符串”可以作为 key？

这是本题最核心的抽象思路。

我们回到“字母异位词”的定义：

两个字符串是异位词
⇔
它们包含的字母种类和数量完全一样

排序后的结果正好满足：

• "eat"→"aet"
• "tea"→"aet"
• "ate"→"aet"

👉只要是异位词，排序后一定完全相同

四、整个算法的“人脑思路”（非常重要）

我用一句话先说结论：

这题不是在处理字符串，而是在“按特征分组”。

你脑子里应该是这样的流程：

1. 给每个字符串提取一个“身份证”（key）
2. 身份证相同的，放到同一组

在这道题中：

• 身份证 = 排序后的字符串

五、逐行用“人话”翻译你的代码

groups={}

建一个空字典，用来“按特征分组”

forsinstrs:

依次拿出每一个字符串

key=''.join(sorted(s))

把字符串变成一个“标准形态”，
所有异位词都会变成同一个 key

ifkeynotingroups:groups[key]=[]

如果这是我第一次看到这个“特征”，
就给它建一个新桶（list）

groups[key].append(s)

把当前字符串，丢进这个特征对应的桶里

📌 注意：

• append 是 list 的行为
• dict 本身不 append

returnlist(groups.values())

字典的 key 不重要了
我要的是每个桶（list）组成的结果

六、这道题本质在考什么？

不是字符串 API，而是：

1️⃣ 你能不能想到“分组”模型

2️⃣ 你能不能为一类对象设计一个稳定的 key

3️⃣ 你是否理解 dict = “key → 容器”

七、一个非常重要的思维迁移（你已经站在门口）

以后你看到题目里出现这些词：

• “分组”
• “归类”
• “相同特征”
• “等价关系”

你应该条件反射想到：

我要用 dict，key 是特征，value 是 list

写法 A（你现在看到的）

ifkeynotingroups:groups[key]=[]groups[key].append(s)

写法 B（你问能不能这样）

ifkeyingroups:groups[key].append(s)else:groups[key]=[s]

答案：可以，完全等价。

它们在逻辑结果上是一样的。

二、两种写法在“思维模型”上的差别

写法 A：先兜底，再统一处理（推荐）

ifkeynotingroups:groups[key]=[]groups[key].append(s)

人脑翻译：

不管这个 key 之前有没有出现过，
我先保证它一定对应一个 list，
然后无条件 append。

📌 特点：

• 主逻辑只有一条append
• 不容易出错
• 非常常见于算法题

写法 B：分情况处理

ifkeyingroups:groups[key].append(s)else:groups[key]=[s]

人脑翻译：

如果桶已经存在，就往里加；
否则新建一个桶并放入第一个元素。

📌 特点：

• 逻辑完全正确
• 但需要在两个分支里分别处理

三、那为什么大多数人写“not in”的版本？

不是因为“更高级”，而是因为：

1️⃣ 主逻辑更清晰

这道题的主动作是：

groups[key].append(s)

而不是“判断”。

写法 A 把判断变成辅助动作。

2️⃣ 更容易扩展

如果你后面要做的不止是append，比如：

groups[key].append(s)groups[key].sort()

用写法 A：

ifkeynotingroups:groups[key]=[]groups[key].append(s)groups[key].sort()

用写法 B 就会更乱。

四、你真正应该记住的“通用模式”

以后你在算法中遇到：

dict 的 value 是 list / set / 计数器

你可以直接形成条件反射：

ifkeynotind:d[key]=初始容器 d[key].更新操作()

五、进一步：为什么 defaultdict 能省掉 if？

你之前看到过这个版本：

fromcollectionsimportdefaultdict groups=defaultdict(list)groups[key].append(s)

它内部自动帮你做了：

ifkeynotingroups:groups[key]=[]

所以你现在理解了普通 dict，再看 defaultdict，会非常自然。

六、一个小“反例”帮助你加深理解

如果你写成这样：

ifkeyingroups:groups[key]=[]groups[key].append(s)

这是错误的，因为：

• 每次 key 已存在时都会把 list 清空

👉 说明你现在问这个问题是非常必要的。

七、总结一句“你现在这个层级最该记住的话”

当 dict 的 value 是一个“可变容器”时，
最稳妥的写法是：先保证它存在，再统一更新。

你现在对 dict + list 的理解，已经覆盖了：

• Two Sum
• 字母异位词分组
• 频率统计
• 按特征分类

不可以省略else。
如果你只写：

ifkeyingroups:groups[key].append(s)

这段代码在key 第一次出现时是错误的。

一、为什么不写else会出问题（关键点）

当key第一次出现时：

keynotingroups

此时：

• if key in groups:条件不成立
• 整个if语句什么都不做
• 你既没有 append，也没有创建groups[key]

接下来如果你还想用：

groups[key].append(s)

就会直接抛出异常：

KeyError

二、逐步演示错误过程（非常重要）

假设：

groups={}s="eat"key="aet"

执行你“不写 else”的版本：

ifkeyingroups:groups[key].append(s)

执行结果：

• key in groups→ False
• 什么都没发生
• groups仍然是{}

字符串"eat"被彻底丢掉了。

三、为什么else在这里是“必须的”

因为你有两个互斥情况：

不写else，你就漏掉了第二种情况。

四、三种“正确且等价”的写法（你应该记住）

✅ 写法 1（最稳妥、最常见）

ifkeynotingroups:groups[key]=[]groups[key].append(s)

✅ 写法 2（你提到的，必须带 else）

ifkeyingroups:groups[key].append(s)else:groups[key]=[s]

✅ 写法 3（defaultdict，理解后再用）

fromcollectionsimportdefaultdict groups=defaultdict(list)groups[key].append(s)

五、为什么大家更推荐“not in + 统一 append”

因为它符合一种通用安全模式：

先保证容器存在，再无条件更新

这在：

• 分组
• 计数
• 聚合
  等问题中非常稳定、不易出错。

七、一句最终结论（给你记住）

当 dict 的 value 是 list 时：
要么写完整的 if–else，
要么用 “if not in → 初始化 → append”，
绝不能只写 if。

下面我按**“为什么是 O(n) + 人脑思路 + 代码逐行解释”来讲128. 最长连续序列。这道题和你前面学的dict / set强相关，是一个认知跃迁题**。

一、题目本质（先定型）

给你一堆无序数字，
找出其中数值连续（x, x+1, x+2 …）的最长长度
——不要求在原数组中位置连续

关键要求：
👉时间复杂度必须是 O(n)

二、为什么不能排序？

最直观的方法是：

nums.sort()

然后线性扫一遍。

❌ 但排序是：

O(n log n)

题目明确要求O(n)，所以排序直接被否定。

三、O(n) 的核心思想（一句话）

用哈希结构，把“查一个数在不在数组中”变成 O(1)，
然后只从“连续序列的起点”开始往右扩展。

四、关键思维跃迁：什么叫“序列的起点”？

假设数组里有：

[1, 2, 3, 4, 100]

1 是不是起点？

• 0 不在数组里 → ✅ 是起点

2 是不是起点？

• 1 在数组里 → ❌ 不是起点

3？

• 2 在 → ❌

100？

• 99 不在 → ✅ 是起点

👉只有“前一个数不存在”的数字，才有资格作为起点

这是这道题O(n) 的核心剪枝。

五、为什么要用 set，而不是 list / dict？

我们需要的操作只有一个：

某个数在不在数组中？

👉set 最合适，因为我们不需要 value。

六、完整算法流程（人脑版）

1. 把所有数字放进一个set

2. 遍历每个数字x

3. 如果x - 1不在 set 中：

   • 说明x是一个连续序列的起点
   • 从x开始，不断检查x+1, x+2, …

4. 更新最长长度

七、标准代码（强烈建议你背这个）

deflongestConsecutive(nums):num_set=set(nums)longest=0forxinnum_set:# 只从“起点”开始ifx-1notinnum_set:cur=x length=1whilecur+1innum_set:cur+=1length+=1longest=max(longest,length)returnlongest

八、逐行“人话解释”（非常重要）

num_set=set(nums)

把数组变成一个“能 O(1) 查存在性”的集合

forxinnum_set:

遍历每一个数（遍历 set，避免重复）

ifx-1notinnum_set:

如果前一个数不存在
👉 我只从“真正的起点”开始数

📌这是保证 O(n) 的关键

whilecur+1innum_set:

一直向右扩展这个连续序列

九、为什么整体是 O(n)？

这是面试官最爱问的一点。

关键原因：

• 每个数只会被“扩展访问一次”
• 非起点的数不会进入 while
• 没有重复扫描

👉 虽然有嵌套while，但总复杂度仍是O(n)

十、这道题在考什么？

不是考你会不会写 while，而是：

1️⃣ 是否能用 set 替代排序

2️⃣ 是否能发现“只从起点扩展”的剪枝

3️⃣ 是否理解 O(n) 的真实含义（不是表面 for + while）

十一、把它和你前面学的题连起来

你现在已经完整覆盖了哈希的三大经典用途。

十二、一个检验你是否真正理解的问题（非常重要）

你可以自己想一想：

如果数组是[1,2,2,3]
为什么用set(nums)反而是正确的？

如果你能回答出：

• “重复元素对连续长度没有贡献”

那说明你对这题已经是理解级掌握，不是背代码。