【leetcode扣热题100(1)】适用于入门、Python代码及详细分析(持续更新)

 先说前面，我的水平很差󿀌如果代码没有特殊标记，则使用力扣官方问题，这里基本记录了我做题时的所有疑惑和解决方案，以及一些补充知识点，希望能方便像我这样的初学者。

目录。

1.两数之和。

2. 异位词分组的字母。

3.最长连续序列。

---

1.两数之和。

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        hashtable = dict()        for i, num in enumerate(nums):            if target - num in hashtable:                return  [hashtable[target - num], i]            hashtable[nums[i]] = i        return []。

1. def twoSum(self, nums: List[int], target: int) -> List[int]:。 定义了 。Solution。 类中的一种方法 。twoSum。，它接受一个整数列表 。nums。 和一个目标值 。target。，并返回包含两个整数索引的列表。
2. hashtable = dict()。 创建空的哈希表（字典），用于存储值及其对应的索引。
3. for i, num in enumerate(nums):。 使用 。enumerate。 函数遍历 。nums。 列表，同时获取元素的索引 。i。 和元素值 。num。。enumerate(a)。 数组a࿰将被接受c;生成一个包含索引和值的迭代器，返回当前元素的索引和元素值。

逻辑点：

1. 哈希表。您可以想象列表，每行存储一个索引和值。在搜索时，只需给出要搜索的数据，哈希函数计算这个数据，得到一个索引，然后在哈希表中找到这个索引，对应项的值通过数组下标直接访问获得。如果更生动地解释，我们可以想象哈希表是字典，查“李”这个词，一般会直接去拼音“L板块，而不是从第一页开始向后翻。为什么我们会下意识地寻找“L"？事实上，这相当于哈希函数，也就是说，计算一个单词的声母。我们去L部分，一页一页地翻字典，找到我们想要的单词。操作是遍历（哈希表的索引可能是链表，而不是单独的数据，存储在链表中具有相同特征的数据，通过遍历搜索。同时，这种复合存储方法也注重速度和空间利用率）。哈希表之所以快，是因为我们对每一个数据都有“量身定做”的索引，直接访问数组下标󿀌因此时间复杂度为O（1）。
2. 这个代码有一个逻辑容易模糊的地方，也就是说，数组的数值存在于哈希表的索引中，数组的索引存在于哈希表的数值中。这是因为当我们在哈希表中找到某个数字时，我们会在哈希表的索引表中找到，代码。

   if target - num in hashtable:。

   这里的hashtable指的是哈希表中索引的部分，而不是哈希表中数据的部分。因为我们正在寻找合格的数字，所以这里的哈希函数是y=x，如果下表为x的数组项不是空的，那就是找到。
3. 这里的哈希表一开始是空的，而不是把所有的数组都存起来，为了避免找到自己。不用担心漏项󿀌第一个数字肯定什么都找不到，它将被存储在࿰中c;以后搜索过的每一项都会被保存下来。只要有一对配对数，即使搜索前一个数字，哈希表中也没有，后一个数字搜索时，前一个数字必须存储在࿰中c;所以一定会找到的。

 。

2. 异位词分组的字母。

class Solution:    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:        mp = collections.defaultdict(list)        for st in strs:            key = "".join(sorted(st))            mp[key].append(st)                return list(mp.values())。

1. def groupAnagrams(self, strs: List[str]) -> List[List[str]]:。 在 。Solution。 在类中定义一个名字 。groupAnagrams。 的方法。它接受字符串列表 。strs。 作为输入�并返回字符串列表的列表。
2. mp = collections.defaultdict(list):。 初始化一个 defaultdict 。mp。，每个键映射到一个列表中。这将用于字母异位字符串的分组。
3. key = “”.join(sorted(st)):。 对字符串 。st。 排序中的字符，并将它们重新组合成字符串key。
4. mp[key].append(st):。 用刚拿到的key做哈希表的索引，将原始字符串 。st。 添加到 defaultdict 。mp。 对应排序字符串 。key。 ￰在列表中c;也完成了分组。
5. return list(mp.values()):。 将 defaultdict 。mp。 值（即字母异位词列表）将其转换为列表并返回。

逻辑点：

1. 列表。列表和链表，数组不同。列表是一种数据结构࿰，按顺序存储c;元素在内存中是连续存储的。在 Python 中，动态数组࿰列表c;可以存储不同类型的元素，支持随机访问（通过索引访问元素）。在最坏的情况下，插入和删除列表可能需要移动大量元素，因此，时间复杂度为 O(n)。
2. dict（字典）。有一个误区，Python 没有专门称为哈希表的数据结构，哈希表的逻辑功能是通过字典的数据结构实现的。Python 字典（dict）实际上是哈希表的一种实现。字典通过哈希函数将键映射到存储位置，实现快速搜索、插入和删除操作。
3. 列表不能作为字典键。 在 Python 中，字典的键必须是不可变的（如字符串、数字、元组等）。刚才说列表是动态数组，因此，如果您想使用列表的数据，您必须首先将其转换为元组等格式。
4. 元组（tuple），如(1, 2,  3, (4, 5))。不同于数组（数组动态），元组是不可变的，元组￰一旦创建c;内容不能修改。圆括号表示元组。
5. defaultdict(list) 直接dict（）的区别。如果访问一个不存在的键，defaultdict将自动创建空列表list作为默认值。这避免了手动检查键是否存在并初始化的步骤。例如：

   # defaultdictfrom使用defalt collections import defaultdictmp = defaultdict(int) # 每个值初始化为intmp类型['];a'] += 1print(mp)  # 输出: defaultdict(<class 'int'>, { 'a': 1}#使用普通dictmp = { }if 'a' not in mp:    mp['a'] = 0mp['a'] += 1print(mp)  # 输出: { 'a': 1}。

6. key = "".join(sorted(st))。

   为什么不能写？

   key = sorted(st)。

   这是因为key = sorted(st) 排序后只会返回字符列表，而不是字符串。我们使用"".join() 将排序后的字符列表连接成字符串，这可以作为哈希表的索引使用。

 。

3.。连续序列最长。

# 我写的是用指针从第二个开始找到连续序列，然后向后移动，记录长度，直到发现第一个不连续，记录当前最大序列长度。然后指针继续从刚才的位置向后移动，以找到一个新的连续序列。整个过程只需要遍历一次class Solution:    def longestConsecutive(self, nums: List[int]) -> int:        if not nums:            return 0                nums.sort()        longest_streak = 1        current_streak = 1        i = 0                while i < len(nums) - 1:            if nums[i] == nums[i + 1]:                i += 1                continue            elif nums[i] + 1 == nums[i + 1]:                current_streak += 1            else:                longest_streak = max(longest_streak, current_streak)                current_streak = 1            i += 1                longest_streak = max(longest_streak, current_streak)        return longest_streak。

相反，这个问题并不难。#xff00c;核心在于如何跳过不必要的遍历，例如，如果已知有x，x+1,x+2,⋯,x+y 连续序列，但我们又重新开始了 x+1，x+2 或者是 x+y 开始尝试匹配#xff0c;那么结果肯定不会比枚举好 x 答案的起点。我用的方法是指针，官方问题如下：：

class Solution:    def longestConsecutive(self, nums: List[int]) -> int:        longest_streak = 0        num_set = set(nums)        for num in num_set:            if num - 1 not in num_set:                current_num = num                current_streak = 1                while current_num + 1 in num_set:                    current_num += 1                    current_streak += 1                longest_streak = max(longest_streak, current_streak)        return longest_streak。

1. num_set = set(nums)。num_set = set(nums)。:。 输入列表 。nums。 转换为集合（哈希表） 。num_set。

，便于快速搜索。不用担心这个哈希表的哈希函数的细节，反正你可以把它理解为一个可以快速检查的表。

1. 逻辑点：

官方问题解决的多余序列跳过部分是使用遍历每个数字，检查哈希表中是否有num-1。如果存在，说明这个数字是前面统计的连续序列的一部分，然后你可以跳过这个数字。 。