一、两数之和
题目：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
方法1：枚举
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for id, num in enumerate(nums):
for idx, num_1 in enumerate(nums[id+1:]):
if num + num_1 == target:
return [id, id + idx + 1]
两个指针，外部循环遍历全部列表，内部循环从原始列表的第二个数开始遍历，枚举所有可能的情况，判断是否等于目标数。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if i != j and nums[i] + nums[j] == target:
return [i, j]
return []
方法2：哈希表
新建一个字典，如果目标值减去当前值的差在字典里，那就说明存在这两个数之和等于目标值。如果没有，那就将当前值添加进字典。
遍历数组，对于每一个数 nums[i]nums[i]nums[i]：
先查找字典中是否存在 target−nums[i]target - nums[i]target−nums[i]，存在则输出 target−nums[i]target - nums[i]target−nums[i] 对应的下标和当前数组的下标 iii。
不存在则在字典中存入 target−nums[i]target - nums[i]target−nums[i] 的下标 i。
def twoSum(self, nums: List[int], target: int) -> List[int]:
numDict = dict()
for i in range(len(nums)):
if target-nums[i] in numDict:
return numDict[target-nums[i]], i
numDict[nums[i]] = i
return [0]
- 首先，创建一个空字典
_dict用来存储数组中每个元素的值和它们对应的索引。这样做的目的是为了快速查找数组中是否存在某个特定的值。 - 然后，使用一个循环遍历数组
nums中的每一个元素。对于当前元素nums[i]，算法尝试找到一个数x，使得x + nums[i] = target。为了找到这样的数x，我们可以将等式重写为x = target - nums[i]，然后查找x是否存在于之前遍历过的元素中。 if target - nums[i] in _dict这行代码就是检查target - nums[i]是否作为一个键（key）存在于字典_dict中。如果存在，这意味着我们找到了两个数nums[i]和x = target - nums[i]，它们的和为target。- 如果找到这样的一个数，
return [_dict[target - nums[i]], i]会返回这两个数的索引。其中_dict[target - nums[i]]是之前存储在字典中的与x相对应的索引，而i是当前nums[i]的索引。
为什么要将减的值（即x对应的索引）放在前面，而将i放在后面呢？这是因为在遍历数组时，当前元素nums[i]的索引i总是大于或等于x对应的索引（因为x是在nums[i]之前出现的）。所以，当我们找到满足条件的一对数时，返回它们的索引时，x对应的索引是较小的，而i是较大的，按照常规逻辑，我们习惯将较小的索引放在前面。
这种方法的关键在于利用哈希表（即 Python 中的字典）来实现快速查找，这使得整个算法的时间复杂度降低到 O(n)，其中 n 是数组nums的长度。
二、49. 字母异位词分组
题目链接地址
建立哈希表（字典），将相同的字母异位词有序化，作为键，变体作为值存储在列表里，最后取出字典的值放在列表里。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
_dict = {}
for i in strs:
n_i = ''.join(sorted(i)) # # 对字符串排序，作为字典的键
if n_i in _dict:
_dict[n_i].append(i) # 如果键已存在，添加到对应的列表中
else:
_dict[n_i] = [i] # 如果键不存在，创建一个新的键并初始化列表
return [i for i in _dict.values()] # 返回字典中所有值的列表
# return list(_dict.values()) # 返回字典中所有值的列表
三、128. 最长连续序列
地址
思路：随机选择一个数，如果该数-1的值不存在于列表中，说明该数字不是有序数列中的中间和后面，是开头；
找到开头，再往后找，也就是加1，如果存在，那就给当前序列长度加一，然后继续往后找，直到不存在为止；
可能有很多连续序列，不可能每个序列长度都存储到一个序列中，所以要找到全局最长，每次和局部最长对比，取最长，这样最后就是全局最长的了。
def longestConsecutive(nums):
# 创建一个集合，用于存储数组中的所有不重复的数字
num_set = set(nums)
longest = 0 # 初始化最长连续序列的长度为0
# 遍历数组中的每个数字
for num in nums:
# 检查当前数字的前一个数字是否不在集合中
# 如果不在，说明当前数字可能是一个连续序列的起点
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 = max(longest, current_streak)
# 返回最长连续序列的长度
return longest
四、283. 移动零
地址
快慢指针，快指针每次走一步，慢指针只在某种条件成立时才走一步。慢指针指向当前应该被替换的位置
条件：快指针遇到了非0值，将其往前替换，也就是跟慢指针的值交换，使得非0往左移动，0往右移动
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 定义慢指针
slow = 0
# 快指针fast遍历列表
for fast in range(len(nums)):
# 当快指针位置不是0
if nums[fast] != 0:
# 替换，将当前快指针位置交换慢指针的值
nums[fast], nums[slow] = nums[slow], nums[fast]
# 交换过了，当前慢指针是非0值，所以往前走一步
slow += 1
return nums
循环过程：
遍历数组时，fast指针负责寻找非零元素。
当fast指针指向的元素不为0时，我们需要将其移到slow指针的位置。这是因为slow指针左侧的所有元素都已经处理过，即它们非零且保持了原有顺序。
交换nums[fast]和nums[slow]之后，我们增加slow指针的值，以指向下一个可能的替换位置。
五、11. 盛最多水的容器
地址
思路：对撞指针。一个从前往后，一个从后往前，计算两者间的面积。判断两个指针位置的高度，哪个低就把哪个指针移动。更新面积。退出条件：指针相遇。
**双指针必要条件：**要有终止条件（一般是两个指针相遇），未达到终止条件时要不断循环，在某个条件下移动这两个指针
本题本质上是 数组长度-1 * 最短高度 的最值问题，需要找到连续最优子数组和子最短高度
class Solution:
def maxArea(self, height: List[int]) -> int:
# 双指针 对撞指针
pre = 0 # 前指针
end = len(height) - 1 # 后指针
marea = 0 # 最大面积
# 当指针没遇到时，循环执行
while pre < end:
# 计算宽度，短板效应，选择两者间最短的
y = (height[pre] if height[pre] < height[end] else height[end])
# 计算长，指针位置的差
x = end - pre # 长
# 计算当前面积
area = x * y
# 更新最大面积
if marea < area:
marea = area
# 如果左指针的值小于右边，就往右走一步
if height[pre] < height[end]:
pre += 1
# 否则，右指针左移
elif height[pre] >= height[end]:
end -= 1
# 从两个端点出发，考虑到所有可能的最优解，并记录过程中的最大值
return marea
六、15. 三数之和
地址
最先想是直接三层遍历，但是一想就不可能是这样，太慢了。
依旧是对撞指针。
三数之和，如果把一个数固定，那就是两数之和。本题是双指针，可以用两个指针来指向另外两个数，成功实现降维。
先将数组进行排序，以保证按顺序查找时，元素值为升序，从而保证所找到的三个元素是不重复的。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
# 排序
# 如果有重复元素，就可以避过
a = sorted(nums)
for i in range(len(a)):
# 将i的情况放在大于0的情况，防止溢出
# 如果遇到重复元素，就跳过，因为题目不让重复
if i >0 and a[i] == a[i-1]:
continue
# 定义左右指针
l, r = i+1, len(a)-1
# 当指针未相撞时，执行循环
while l < r:
# 如果当前遍历的位置和左右指针的值和为1，表明找到解了，添加到答案，然后移动左右指针
if a[i] + a[l] + a[r] == 0:
res.append([a[i], a[l], a[r]])
l += 1
r -= 1
# 如果说小于0，因为我们是排序了的，左边肯定比右边小，i又不能变，所以肯定是l太靠左了，加一右移
elif a[i] + a[l] + a[r] < 0:
l += 1
# 反之就是右边太大，左移
else:
r -= 1
# 虽然说上面是跳过了重复元素，但是也存在两个重复元素和其他的重复的都存在，导致有多个解是相同的
# 将答案的每个元素排序后转为元组，因为列表不可哈希，用不了集合。集合去重
unique_tuples = set(tuple(sorted(sublist)) for sublist in res) # 去重并转换为集合
nr = [list(tup) for tup in unique_tuples] # 将元组转换回列表
return(nr)
![[算法沉淀记录] 排序算法 —— 选择排序](https://img-blog.csdnimg.cn/direct/823c15f825f94fa9800b7dc7b8cc07b5.png)
