📝 Leetcode 刷题记录 🌀
记录刷过的Leetcode..
Leetcode 1: Two Sum 两数之和
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
难度：简单
标签：数组、哈希表
题解：
① 暴力枚举
思路：很简单，但是时间复杂度较高…
时间复杂度：O(n^2)
空间复杂度：O(1)
# 因为需要索引，所以要先获取nums的长度
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]
② 哈希表
关键在于：降低target-x的复杂度，从O(n)降到O(1)
hashtable的作用：
1.存储已经遍历过的数字：把nums中的数字作为key，索引作为value
2.快速查找互补数字：当互补的数在hashtable中时，直接返回这一组数字
from typing import List
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:
print(f'hashtable: {hashtable}')
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
if __name__ == '__main__':
sol = Solution()
nums = [2, 7, 11, 15]
target = 9
print(sol.twoSum(nums, target))
时间复杂度：O(n), n是数组长度
空间复杂度：O(n)，n是数组长度
Leetcode 15: 3Sum 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
难度：中等
标签：数组、双指针、排序
题解：
① 暴力破解
思路：很简单，但是时间复杂度较高，超时时间限制…
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
# print(f'nums: {nums}')
length = len(nums)
i, j, k = 0, 0, 0
ret_list = list()
for i in range(length):
for j in range(i + 1, length):
for k in range(j + 1, length):
# print(f'i={i}, j={j}, k={k}')
if nums[i] + nums[j] + nums[k] == 0:
# print('====yes========')
if [nums[i], nums[j], nums[k]] not in ret_list:
ret_list.append([nums[i], nums[j], nums[k]])
return ret_list
时间复杂度：O(n^3)
- 排序：O(nlogn)
- 三重循环：O(n^3)
空间复杂度：
- 排序：?
- 三元组列表: ?
② 排序+双指针
思路：固定第一个数，然后让第二个数和第三个数进行双指针遍历 \
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
# print(f"nums: {nums}")
length = len(nums)
ret_list = list() # 存放结果
# 第一个数做外循环
for i in range(length-2):
# 第二个数和第三个数：双指针
left, right = i+1, length-1
while left < right:
# print(f"i={i}, left: {left}, right: {right}")
# print(f"nums[i]={nums[i]}, mums[left]: {nums[left]}, nums[right]: {nums[right]}")
if nums[i] + nums[left] + nums[right] == 0:
if [nums[i], nums[left], nums[right]] not in ret_list:
ret_list.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
elif nums[i] + nums[left] + nums[right] > 0:
right -= 1
# print(f"ret_list: {ret_list}")
return ret_list
提交代码后发现，依然是超出时间范围。
原因：去重逻辑不对，通过 if [nums[i], nums[left], nums[right]] not in ret_list去重，实际上把时间复杂度提高了O(n^3)，因为最坏情况下，每次都要遍历结果列表。
优化去重逻辑，代码如下：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
# print(f"nums: {nums}")
length = len(nums)
ret_list = list() # 存放结果
# 第一个数做外循环
for i in range(length - 2):
# 最外层去重：
if i > 0 and nums[i] == nums[i - 1]:
continue
# 外层优化：提前终止
if nums[i] > 0:
break
# 第二个数和第三个数：双指针
left, right = i + 1, length - 1
while left < right:
# print(i, left, right)
if nums[i] + nums[left] + nums[right] == 0:
ret_list.append([nums[i], nums[left], nums[right]])
# 去重逻辑!!!
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
else:
right -= 1
return ret_list
时间复杂度：O(n^2)
- 排序：O(nlogn)
- 双指针遍历：O(n^2)
空间复杂度：
- 排序：sorted()使用TimSort，最好情况下为O(1)，即原地排序；最坏情况为O(n)，即需要额外空间来存储排序后的数组
- 结果列表ret_list：最坏情况下，为O(n^2)
- 额外常量（length、left、right、i）
③ HashhSet
类似于两数相加的哈希表解法，使用哈希表来存储已经遍历过的数字，然后遍历哈希表，找到互补的数字。
在这里，固定住前两个数，然后遍历哈希表，找到互补的数字。 解法：Todo
Leetcode 18: 4Sum 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2： 输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
难度：中等
标签：数组、双指针、排序
题解：
① 暴力枚举
思路：很简单，但是时间复杂度较高…
时间复杂度：O(n^4)
空间复杂度：O(1)
② 双指针
需要注意的就是：一些提前终止的优化（剪枝？）
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
length = len(nums)
nums = sorted(nums) # 等价于：nums.sort()
print(f'nums: {nums}')
ret_list = list()
for a in range(length - 3):
if a > 0 and nums[a] == nums[a - 1]:
continue
if nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
break
if nums[a] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target:
continue
for b in range(a + 1, length - 2):
if b - a > 1 and nums[b] == nums[b - 1]:
continue
if nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target:
break
if nums[a] + nums[b] + nums[length - 1] + nums[length - 2] < target:
continue
c, d = b + 1, length - 1
while c < d:
print(f'a={a}, b={b}, c={c}, d={d}')
if nums[a] + nums[b] + nums[c] + nums[d] < target:
c += 1
elif nums[a] + nums[b] + nums[c] + nums[d] > target:
d -= 1
else:
ret_list.append([nums[a], nums[b], nums[c], nums[d]])
while c < d and nums[c] == nums[c + 1]:
c += 1
while c < d and nums[d] == nums[d - 1]:
d -= 1
d -= 1
c += 1
return ret_list
时间复杂度：O(n^3)
- 外层循环需要 O(n)
- 中层循环需要 O(n)
- 内层的双指针遍历需要 O(n)
空间复杂度：O(1)
- 只需要常数级别的存储空间。返回值不计入空间复杂度。
Leetcode 49: Group Anagrams 字母异位词分组
Leetcode 49: Group Anagrams 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]示例 2:
输入: strs = [””]
输出: [[””]]示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]仅包含小写字母
难度：中等
标签：数组、哈希表、字符串、排序
题解：
① 字母排序
思路：将每个字符串排序，然后比较排序后的字符串是否相同【因为字母异位词排序后是一样的】
→ 模式识别：一旦需要根据特征进行归类，就应该利用散列表
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashtable = {}
for word in strs: # eat
# print(f'word: {word}')
# print(f"sorted(word): {''.join(sorted(word))}")
if ''.join(sorted(word)) not in hashtable:
hashtable[''.join(sorted(word))] = [word]
else:
hashtable[''.join(sorted(word))].append(word)
# print(f'hashtable: {hashtable}')
# print(list(hashtable.values()))
return list(hashtable.values())
询问gemini，给出的优化建议：
1.因为列表不可哈希，因此使用了''.join(sorted(word))将列表转化为字符串，从而可以作为key → 为了提高效率，可以使用元组作为key，修改为：tuple(sorted(word))
2.使用了if..else来判断word是否在hashtable中 → 可以使用collections.defaultdict()来简化代码【defaultdict：为不存在的键提供一个默认值】。注意：defaultdict()要给参数list，即创建一个空的列表作为默认值。
优化后的代码为：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashtable = defaultdict(list)
for word in strs:
hashtable[tuple(sorted(word))].append(word)
# print(f'hashtable: {hashtable}')
# print(list(hashtable.values()))
return list(hashtable.values())
时间复杂度：O(n * klogk)
- 遍历数组strs,需要O(n)时间，n是数组长度
- 对于每个字符串需要排序，sorted(word)需要O(klogk)时间，k是字符串平均长度
- 哈希表的插入和查找操作都是O(1)时间
空间复杂度：O(n * k)
- hashtable最多存储n个键值对，n是数组长度
- 最坏的情况下，所有字符串都是字母异位词，此时hashtable存储了n个数组，每个数字长度为1（字符串长度为k）
② 字符计数
思路：
对应每个单词，如果其字符串中每个字符出现的次数相同，那么它们是字母异位词，因此可以利用字符串的每个字符出现的次数作为key，将每个单词存储在hashtable中
题目已经说明了只会存在小写字母，因此可以利用长度为26的数组(元组)来存储每个字符出现的次数
难点在于：构造26个字符的元组作为key –> ord()函数
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashtable = defaultdict(list)
for word in strs:
key = [0] * 26
for ch in word:
key[ord(ch) - ord('a')] += 1
hashtable[tuple(key)].append(word)
# print(f'hashtable: {hashtable}')
return list(hashtable.values())
时间复杂度：O(n * k)
- 遍历数组strs,需要O(n)时间，n是数组长度
- 对于每个字符串需要遍历每个字符，计算每个字符出现的次数，需要O(k)时间，k是字符串平均长度
- 哈希表的插入和查找操作都是O(1)时间
空间复杂度：O(n * k)
- 哈希表：最多存储n个键值对，n是数组长度; 每个键值对的值为列表，列表长度为k
- 技术数组：长度为固定的26，复杂度为O(1)
Leetcode 128: Longest Consecutive Sequence 最长连续序列
Leetcode 128: Longest Consecutive Sequence 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9示例 3：
输入：nums = [1,0,1,2]
输出：3
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
难度：中等
标签：数组、哈希表、并查集
分析：此题的难点在于：不能使用排序，因为排序的时间复杂度是O(nlogn)，超过了O(n)…
题解：
① 哈希表/哈希集合
另辟蹊径：把nums转换为哈希集合【哈希集合中判断数字是否存在的时间复杂度为O(1)】，然后遍历哈希集合！
重点：遍历时，不以x为起点，而是以x-1为起点！【以x-1为起点的序列，一定比以x为起点的序列更长】
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums_set = set(nums)
print(f"nums_set: {nums_set}")
target_len = 1
# 为空
if not nums_set:
return 0
for num in nums_set:
if num - 1 in nums_set: # small_one in nums_set, 直接跳过即可
continue
bigger_one = num + 1
while bigger_one in nums_set: # 判断bigger_one是否在nums_set中，while不断往上+1
bigger_one += 1
# bigger_one - num + 1 为该次循环的最大值，和target_num（最长序列值）做比较，若长，则返回
if bigger_one - num + 1 > target_len:
target_len = bigger_one - num
return target_len
时间复杂度：O(n)
- 集合去重：O(n)
- 遍历哈希集合：O(n)
空间复杂度：O(n)
- 集合：nums_set最多存储n个元素
② 并查集 问了gemini，此题还有一种并查集的解法。
并查集（Union-Find）是一种用于处理集合合并和查询问题的数据结构。
集合表示：
- 并查集使用树形结构来表示集合。
- 每个集合都有一棵树，树的根节点代表这个集合。
- 每个元素都是树中的一个节点。
父节点：
- 每个节点都有一个父节点，用于指向其在树中的上级节点。
- 根节点的父节点指向自身。
根节点：
- 根节点是树的最高级节点，代表一个集合。
- 通过查找根节点，可以确定一个元素属于哪个集合。
并查集的核心操作：
- 查找（Find）：
- 从给定的元素开始，沿着父节点向上查找，直到找到根节点。
- 为了提高查找效率，可以使用“路径压缩”优化，将查找路径上的所有节点的父节点直接指向根节点。
- 合并（Union）：
- 查找两个元素各自的根节点。
- 如果根节点不同，则将一个根节点的父节点指向另一个根节点，从而合并两个集合。
- 为了提高合并效率，可以使用“按秩合并”或者“按大小合并”的优化，减少树的高度。
并查集的应用场景：
- 判断连通性：例如，判断网络中的两个节点是否连通。
- 查找朋友圈：例如，查找社交网络中属于同一个朋友圈的用户。
- 最小生成树：例如，在 Kruskal 算法中，用于判断两个节点是否属于同一个连通分量。
- 解决一些图论问题
并查集的优点：
- 高效：查找和合并操作的时间复杂度接近 O(1)。
- 简单：代码实现相对简单。
并查集的缺点：
- 不支持集合分割： 并查集只能合并集合，不能分割集合。
这里先给出代码，后续再研究：（树）
class UnionFind:
# 初始化并查集，为每个元素创建一个独立的集合
def __init__(self, nums):
self.parent = {num: num for num in nums} # 初始化父节点
self.size = {num: 1 for num in nums} # 初始化集合大小
# 查找元素的根节点，并进行路径压缩优化
def find(self, num):
if self.parent[num] != num:
self.parent[num] = self.find(self.parent[num]) # 路径压缩
return self.parent[num]
# 合并两个元素所在的集合，并进行按大小合并优化
def union(self, num1, num2):
root1 = self.find(num1)
root2 = self.find(num2)
if root1 != root2:
if self.size[root1] < self.size[root2]: # 按大小合并
self.parent[root1] = root2
self.size[root2] += self.size[root1]
else:
self.parent[root2] = root1
self.size[root1] += self.size[root2]
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
num_set = set(nums)
uf = UnionFind(num_set)
# 遍历集合num_set，对于每个元素num，如果num+1存在于集合中，则合并num和num+1所在的集合
for num in num_set:
if num + 1 in num_set:
uf.union(num, num + 1)
# 遍历集合num_set，计算每个集合的大小，并找出最大的集合
max_len = 0
for num in num_set:
max_len = max(max_len, uf.size[uf.find(num)])
return max_len
时间复杂度：O(n)
- 初始化并查集：O(n)
- 遍历集合：O(n)
- 查找和合并操作：O(1)
空间复杂度：O(n)
- 并查集：需要O(n)空间存储父节点和集合大小
Leetcode 167: Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
Leetcode 167: Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
提示：
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 只会存在一个有效答案
难度：中等
标签：数组、双指针、二分查找
分析：
题目难点在于，使用常量级的额外空间，即空间复杂度为O(1)。
题解：
① 双指针
思路： 双指针的经典题目，比较简单了.. 注意：本题在循环条件中，没有判断left指针超过right指针的情况，因为题目已经保证了一定存在一个有效答案，但要注意在其他类似的题目中，需要判断left指针超过right指针的情况。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
left, right = 0, length - 1
while numbers[left] + numbers[right] != target:
if numbers[left] + numbers[right] > target:
right -= 1
else:
left += 1
# 注意：返回时，索引不是从0开始，要对应+1
return [left+1, right+1]
这里也提供下官方题解：(考虑了left不超过right的场景，注意循环条件的结束使用的是这个！)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low, high = 0, len(numbers) - 1
while low < high:
total = numbers[low] + numbers[high]
if total == target:
return [low + 1, high + 1]
elif total < target:
low += 1
else:
high -= 1
return [-1, -1]
时间复杂度：O(n)
- 最坏情况下，需要遍历整个数组，时间复杂度为O(n)
空间复杂度：O(1)
- 只使用了几个常量（length, left, right）
② 暴力破解
虽然效率不高，但也是一种解法…提交答案发现：超出时间限制…
这里其实可以通过‘输入数组是有序的’这个条件来排除这个答案的，因为暴力破解用不到这个条件…
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
for i in range(0, length-1):
for j in range(i+1, length):
if numbers[i] + numbers[j] == target:
return [i+1, j+1]
return []
时间复杂度：O(n^2)
空间复杂度：O(1)
③ 散列法
实际上就是Leetcode 1. Two Sum的解法，使用哈希表来存储每个元素的值和索引，然后遍历数组，查找target-numbers[i]是否在哈希表中，如果存在，则返回两个索引。 但是：注意审题，题目要求空间复杂度为O(1)，所以不能使用哈希表…
时间复杂度：O(n)
空间复杂度：O(n)
④ 二分查找
实际上这题，当看到有序数组时，可以往二分查找的方向思考…
这里可以作为二分查找的变通，可以先固定一个数，然后在剩下的数组中使用二分查找查找target-numbers[i]是否存在。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
print(f'length: {length}')
for left in range(length):
# 在left+1和length-1中二分查找target-numbers[left]
start, end = left+1, length - 1
while start <= end:
mid = (start + end) // 2
if numbers[left] + numbers[mid] == target:
return [left+1, mid+1]
elif numbers[left] + numbers[mid] > target:
end = mid - 1
else:
start = mid + 1
return []
时间复杂度：O(nlogn)
- 外层循环：O(n)
- 内层二分查找：O(logn)
空间复杂度：O(1)
- 只使用了几个常量（length, start, end, mid）
Leetcode xx: xx
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
难度：简单
标签：数组、哈希表
题解：
① 暴力枚举
思路：很简单，但是时间复杂度较高…
时间复杂度：O(n^2)
空间复杂度：O(1)