🧮 Week 1 Day 1 — LeetCode Hot100学习笔记
📘 1. 两数之和（Two Sum）
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
🔹 解法一：暴力遍历
思路：
通过两层循环遍历数组中所有可能的两数组合，找到满足 nums[i] + nums[j] == target 的一对数。
关键函数：
enumerate() 函数返回 (索引, 值)，方便同时获取元素和下标。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, x in enumerate(nums):
for j in range(i + 1, len(nums)):
if x + nums[j] == target:
return [i, j]
时间复杂度： O(n²)
空间复杂度： O(1)
🔹 解法二：哈希表（空间换时间）
思路：
使用哈希表存储遍历过的数字及其索引，以便在 O(1) 时间内判断目标差值是否存在。
-
键（key）：当前数字
x -
值（value）：索引
i
实现代码：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
idx = {}
for i, x in enumerate(nums):
if target - x in idx:
return [idx[target - x], i]
idx[x] = i
时间复杂度： O(n)
空间复杂度： O(n)
📗 2. 字母异位词分组（Group Anagrams）
题目描述：
给你一个字符串数组 strs，请将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"], ["nat","tan"], ["ate","eat","tea"]]
🔹 解法：哈希表 + 排序键
思路：
-
对每个字符串进行排序，得到标准形式作为哈希表的键；
-
相同键的字符串属于同一组。
实现代码：
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
sort_s = ''.join(sorted(s)) # 对字符串排序作为 key
d[sort_s].append(s)
return list(d.values())
🧩 关键细节：
-
defaultdict(list)的作用：-
来自
collections模块。 -
若访问不存在的 key，会自动创建该 key，并初始化为空列表。
-
避免手动判断是否存在键：
if key not in d: d[key] = []
-
-
sorted(s)与''.join(...)：-
sorted(s)：返回排序后的字符列表。
例：sorted("eat") → ['a', 'e', 't'] -
''.join(...)：将字符列表拼接为字符串。
例：['a', 'e', 't'] → "aet"
-
时间复杂度： O(n·klogk)，其中 k 为字符串平均长度
空间复杂度： O(n·k)
📙 3. 最长连续序列（Longest Consecutive Sequence）
题目描述：
给定一个未排序的整数数组 nums，找出 数字连续的最长序列 的长度。
要求：时间复杂度为 O(n)。
🔹 解法：哈希集合（Set）
核心思想：
-
将数组转换为集合
set(nums)，方便 O(1) 查找。 -
仅从“序列起点”开始向后遍历。
-
如果
x-1不在集合中，说明x是新序列的起点。 -
然后持续查找
x+1, x+2, ...是否在集合中。
-
实现代码：
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums)
ans = 0
for x in st:
if x - 1 in st: # 如果前一个数存在，则不是序列起点
continue
y = x + 1
while y in st:
y += 1
ans = max(ans, y - x)
return ans
时间复杂度： O(n)
空间复杂度： O(n)