【枚举右，维护左】第一章（第1~7题）

枚举右，维护左

枚举右，维护左用于双变量问题
例如两数之和 $a_i + a_j = t$ 。可以枚举右边的 $a_j$ ，转换成单变量问题，也就是在左边查找是否有 $a_i=t−a_j$ ，这可以用哈希表维护。

1. 两数之和

找到两个数加和等于target

1.1 枚举右维护左

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for i, x in enumerate(nums):  # x=nums[i]for j in range(i + 1, len(nums)):  # 枚举 i 右边的 jif x + nums[j] == target:  # 满足要求return [i, j]  # 返回两个数的下标# 这里无需 return，因为题目保证有解作者：灵茶山艾府
链接：https://leetcode.cn/problems/two-sum/solutions/2326193/dong-hua-cong-liang-shu-zhi-he-zhong-wo-0yvmj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

时间复杂度： $O(n^2)$ ，其中 n 为 nums 的长度。
空间复杂度： $O (1)$ 。仅用到若干额外变量。

1.2 枚举右，维护左 + 哈希表

利用哈希表存储，所有的元素与对应的索引！
一次遍历，每次检查当前元素是否有之前的元素（存在字典中！）与之匹配！

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:idx = {}for j, x in enumerate(nums): #从左到右遍历所有元素if target - x in idx:  # 如果在字典中已经存在了！target-x  说明满足了 当前x + 之前某个x = t!对应索引！j， idx[nums[target-x]]return [j,idx[target-x], ]  idx[x] = j # 键nums[j] 值j索引，保存当前j x到字典中！

1512. 好数对的数目

给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组好数对。
返回好数对的数目。

示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

枚举 $n u m s [j]$ ，同时用哈希表维护 $n u m s [j]$ 左边每个数字出现的次数！
例如 $[1, 1, 2, 1]$ ，遍历到 $j = 3$ 时， $c n t [1] = 2$ ，那么就找两个好数对，就把 $2$ 加入答案。

解法

注意:
- 需要 from collections import defaultdict来调用defaultdict
- 为什么ans += cnt[x]就是答案，也就是对数？新出现的x + x之前出现的次数 == 目前属于x的对数
- 为什么先更新答案，再加入答案（记录对数）？
  - 因为题目要求了要 $i < j$ 才是算是满足条件的一对！i==j不能算是一对！！！

class Solution:def numIdenticalPairs(self, nums: List[int]) -> int:# 枚举右 维护左# 对于右边aj，在aj左边查找 是否有 满足条件的ai# “是否有”的问题可以用hash表# 最好用defaultdictcnt = defaultdict(int)ans = 0for x in nums:ans += cnt[x]cnt[x] += 1return ans

2001. 可互换矩形的对数

使用“枚举右，维护左 + 哈希表”的算法思想来解决“2001. 可互换矩形的组数”这道题目的Python代码及详细解释：

代码实现

from typing import Listclass Solution:def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:cnt = {}  # 用于记录每种宽高比出现的次数ans = 0for i in range(len(rectangles)):width, height = rectangles[i]ratio = width / height  # 计算当前矩形的宽高比if ratio in cnt:# 如果当前宽高比已经在哈希表中出现过，说明找到了可互换的矩形# 那么可互换矩形的对数要加上已经出现的该宽高比的矩形个数ans += cnt[ratio]# 将当前宽高比的出现次数加1，维护哈希表if ratio not in cnt:cnt[ratio] = 1else:cnt[ratio] += 1return ans

代码解释

整体思路：
按照“枚举右，维护左”的思想，我们从左到右遍历数组 rectangles（这里把每个矩形看作数组中的一个元素），对于每个矩形（也就是“枚举右”的过程），计算它的宽高比（作为关键的特征值），然后利用哈希表 cnt 来“维护左”，即记录已经遍历过的矩形中每种宽高比出现的次数。在遍历过程中，每当发现当前矩形的宽高比在哈希表中已经存在时，就说明找到了与之前某个矩形可互换的情况，此时可以根据已经出现的该宽高比的矩形个数来计算新增的可互换矩形对数，并累加到结果 ans 中。
具体步骤：
- 初始化哈希表和结果变量：

cnt = {}  # 用于记录每种宽高比出现的次数
ans = 0

创建一个空的哈希表 cnt，它的键将是矩形的宽高比（浮点数类型），值是对应宽高比出现的次数（整数类型）。同时初始化变量 ans 为 0，用于记录最终可互换矩形的对数，后续会不断更新这个值。

遍历矩形数组并处理：

for i in range(len(rectangles)):width, height = rectangles[i]ratio = width / height  # 计算当前矩形的宽高比if ratio in cnt:# 如果当前宽高比已经在哈希表中出现过，说明找到了可互换的矩形# 那么可互换矩形的对数要加上已经出现的该宽高比的矩形个数ans += cnt[ratio]# 将当前宽高比的出现次数加1，维护哈希表if ratio not in cnt:cnt[ratio] = 1else:cnt[ratio] += 1

首先通过循环遍历 rectangles 数组，对于每个位置 i，取出当前矩形的宽度 width 和高度 height，并计算其宽高比 ratio（使用实数除法，符合题目要求判断两个矩形是否可互换的条件）。
接着判断计算得到的宽高比 ratio 是否已经在哈希表 cnt 中：
如果在哈希表中，说明当前矩形与之前出现过的具有相同宽高比的矩形是可互换的。此时，可互换矩形的对数需要加上已经出现的该宽高比的矩形个数，因为对于已经存在的每个该宽高比的矩形，都能和当前矩形组成一对可互换矩形，所以通过 ans += cnt[ratio] 将对应的对数累加到 ans 中。
无论宽高比 ratio 是否在哈希表中，都需要对哈希表进行维护，即更新该宽高比的出现次数。如果 ratio 不在哈希表中，说明是第一次出现这个宽高比，将其添加到哈希表中，并设置出现次数为 1（通过 cnt[ratio] = 1 实现）；如果 ratio 已经在哈希表中，就将其出现次数加 1（通过 cnt[ratio] += 1 实现）。

返回结果：

return ans

在遍历完整个 rectangles 数组后，ans 中就存储了所有可互换矩形的对数，直接返回这个值即可。

时间和空间复杂度分析

时间复杂度：
需要遍历一次 rectangles 数组，时间复杂度为 $O (n)$ ，其中 n 是矩形的个数（也就是 rectangles 数组的长度）。在每次遍历过程中，对哈希表进行查找、插入和更新操作，平均时间复杂度都接近 $O (1)$ ，所以总的时间复杂度主要由遍历数组这一步决定，为 $O (n)$ 。
空间复杂度：
哈希表 cnt 中最多会存储 n 种不同的宽高比（在最坏情况下，每个矩形的宽高比都不同），所以空间复杂度为 $O (n)$ ，这里 n 同样是矩形的个数。

通过使用“枚举右，维护左 + 哈希表”的算法思想，能够高效地解决这道题目，避免了暴力解法中两层嵌套循环去比较所有矩形对的高时间复杂度情况（暴力解法时间复杂度为 $O(n^2)$ ），满足题目要求并在合理的时间和空间复杂度范围内得出结果呀。希望这个解释对你有帮助，要是还有疑问可以随时问我哦。

简化代码——defaultdict实现

以下是使用Python内置的 collections 模块中的 defaultdict 类来实现同样功能的代码，相比于之前的代码在一定程度上更加简洁，它本质上也是一种哈希表的应用形式，利用了 defaultdict 的默认值初始化特性简化了代码逻辑。

from typing import List
from collections import defaultdictclass Solution:def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:cnt = defaultdict(int)  # 使用defaultdict，默认值为0，用于记录每种宽高比出现的次数ans = 0for rect in rectangles:width, height = rectratio = width / heightans += cnt[ratio]  # 直接累加对应宽高比已出现的次数cnt[ratio] += 1  # 宽高比出现次数加1return ans

代码解释

1. `defaultdict` 的引入

from collections import defaultdict：首先从Python的 collections 模块中导入 defaultdict 类。defaultdict 是Python内置的一个字典的子类，它的特点是在访问不存在的键时，会使用一个默认的工厂函数来初始化这个键对应的值，而不是像普通字典那样抛出 KeyError 异常。在这里，我们初始化 defaultdict 时传入 int 作为参数，这意味着当访问不存在的键时，它会自动将该键对应的值初始化为 0（因为 int() 函数返回 0），这正好符合我们统计宽高比出现次数的需求，不需要像之前那样手动判断键是否存在然后进行初始化操作了。

2. 主要逻辑部分

cnt = defaultdict(int)  # 使用defaultdict，默认值为0，用于记录每种宽高比出现的次数
ans = 0
for rect in rectangles:width, height = rectratio = width / heightans += cnt[ratio]  # 直接累加对应宽高比已出现的次数cnt[ratio] += 1  # 宽高比出现次数加1

首先创建了 cnt 这个 defaultdict 对象，它将用于记录每种宽高比出现的次数，初始时所有键对应的默认值都是 0。
初始化 ans 为 0，用于存储最终可互换矩形的对数，后续会在循环中不断累加更新。
然后通过循环遍历 rectangles 数组，对于每个矩形 rect，提取出宽度 width 和高度 height，并计算宽高比 ratio。
接下来，直接通过 ans += cnt[ratio] 来累加可互换矩形的对数，因为如果 ratio 这个宽高比之前已经出现过，cnt[ratio] 就是之前出现的次数，直接累加到 ans 中；如果 ratio 是第一次出现，由于 defaultdict 的特性，cnt[ratio] 的默认值为 0，这也不会影响累加的逻辑（相当于加 0）。
最后，通过 cnt[ratio] += 1 将当前宽高比 ratio 的出现次数加 1，用于更新统计信息，方便后续遇到相同宽高比的矩形时继续正确累加可互换矩形的对数。

3. 返回结果

return ans

在遍历完整个 rectangles 数组后，ans 中就存储了所有可互换矩形的对数，直接返回这个值即可。

整体来说，使用 defaultdict 简化了代码中对哈希表键是否存在的判断以及初始化操作，让代码更加简洁清晰，同时依然保持了利用哈希表来高效统计宽高比出现次数从而计算可互换矩形对数的核心逻辑，时间复杂度和空间复杂度与之前的实现方式是一样的（时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ ，其中 n 是矩形的个数）。

219. 存在重复元素II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

from typing import Listclass Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:num_dict = {}  # 字典记录当前值和索引for idx, num in enumerate(nums):if num in num_dict and abs(idx - num_dict[num]) <= k:return Truenum_dict[num] = idxreturn False

以下是结合上述两种写法（包含滑动窗口元素删除逻辑以及严谨判断的完整写法），使用“枚举右，维护左 + 哈希表”思想来解决“219. 存在重复元素 II”这道题的详细题解，包含Python代码及对应的解释说明：

代码实现

from typing import Listclass Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:window = {}  # 用于记录窗口内元素及其对应的索引for index, num in enumerate(nums):# 检查当前元素是否在窗口内已出现过，且索引差是否满足条件if num in window and index - window[num] <= k:return True# 将当前元素及其索引存入窗口字典中window[num] = index# 当索引大于等于k时，维护窗口大小，删除窗口最左边元素对应的记录if index >= k:del_key = nums[index - k]if del_key in window and window[del_key] == index - k:del window[del_key]return False

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:window = {}  # 用于记录窗口内元素及其对应的索引# 获取当前索引index和numfor index, num in enumerate(nums):# if num in window and index - window[num] <= k:return True# 否则，字典中记录当前的num和indexwindow[num] = index# 如果index已经大于k了，需要删除元素if index >= k:# 需要被删的就是del_keydel_key = nums[index - k]# #if del_key in window and window[del_key] == index - k:del window[del_key]return False

代码解释

1. 整体思路

通过从左到右遍历数组 nums（“枚举右”），利用哈希表 window 来记录已经遍历过的元素及其索引，以此“维护左”，同时通过控制窗口大小来确保只考虑距离当前位置在 k 范围内的元素。在遍历过程中，一旦发现当前元素在窗口内已经存在且与上次出现的索引距离小于等于 k，就说明找到了符合题目要求的重复元素，返回 True；若遍历完整个数组都未发现这样的情况，则返回 False。

2. 具体步骤

初始化窗口字典：

window = {}  # 用于记录窗口内元素及其对应的索引

创建一个空的哈希表 window，它的键用于存储数组 nums 中的元素值，值用于存储对应元素在数组中出现的索引，以此来记录窗口内元素及其出现位置的信息。

遍历数组并处理：

for index, num in enumerate(nums):# 检查当前元素是否在窗口内已出现过，且索引差是否满足条件if num in window and index - window[num] <= k:return True# 将当前元素及其索引存入窗口字典中window[num] = index# 当索引大于等于k时，维护窗口大小，删除窗口最左边元素对应的记录if index >= k:del_key = nums[index - k]if del_key in window and window[del_key] == index - k:del window[del_key]

- **检查重复元素及索引差条件**：

通过 enumerate 函数获取数组 nums 中每个元素的索引 index 和元素值 num，然后在循环中进行判断。对于每个元素，首先使用 num in window 检查当前元素 num 是否已经在 window 字典中，若存在，再通过 index - window[num] <= k 判断当前索引 index 与该元素上次在字典中记录的索引（通过 window[num] 获取）的差值是否小于等于 k。如果这两个条件都满足，就意味着找到了满足 nums[i] == nums[j] 且 abs(i - j) <= k（这里 i 为之前记录的索引，j 为当前索引）的两个不同索引，符合题目要求，直接返回 True。
- 更新窗口字典：
如果当前元素不在 window 字典中，或者虽然在字典中但不满足索引差条件，就需要将当前元素 num 及其索引 index 存入 window 字典中，通过 window[num] = index 来更新元素的索引记录，这样后续遇到相同元素时可以准确判断索引差情况。
- 维护窗口大小（删除窗口最左边元素记录）：
当遍历的索引 index 大于等于 k 时，意味着窗口已经“移动”到了新的位置，需要把窗口最左边（也就是最早进入窗口的元素）对应的键值对从 window 字典中删除，以保证窗口内只保留距离当前位置在 k 范围内的元素记录。
首先通过 del_key = nums[index - k] 获取当前窗口最左边元素的值（因为 index - k 正好指向了窗口最左边元素的索引，通过 nums 数组获取对应元素值）。然后使用 if del_key in window and window[del_key] == index - k: 进行严谨的条件判断，确保要删除的元素确实在字典中，并且其记录的索引就是当前窗口最左边应该被删除的那个索引位置（防止出现意外情况，比如相同元素值在更后面又出现了，导致字典中对应的值被更新了，不符合预期的窗口删除逻辑），只有满足这个条件时，才通过 del window[del_key] 真正删除 window 字典中的对应键值对。

返回结果：

return False

如果遍历完整个数组 nums 都没有找到满足条件的重复元素情况（即没有执行到 return True 的逻辑），则说明不存在符合要求的两个索引，此时返回 False。

时间和空间复杂度分析

时间复杂度：
遍历数组 nums 一次，时间复杂度为 $O (n)$ ，其中 n 是数组 nums 的长度。在每次遍历过程中，对哈希表 window 进行查找、插入和更新操作的平均时间复杂度接近 $O (1)$ ，虽然有删除窗口最左边元素的操作，但整体来看，这些操作的时间复杂度依然是线性的，所以总的时间复杂度主要由遍历数组这一步决定，为 $O (n)$ 。
空间复杂度：
哈希表 window 中最多会存储 min(n, k + 1) 个不同的元素（在最坏情况下，数组中前 k + 1 个元素都不同或者整个数组元素都不同，但不会超过 n 个元素），所以空间复杂度为 $O (min (n, k + 1))$ ，这里 n 是数组 nums 的长度，k 是给定的距离限制参数。

通过这样的代码实现，严谨地运用了“枚举右，维护左 + 哈希表”的思想以及滑动窗口的元素管理逻辑，能够高效且准确地判断数组中是否存在满足条件的重复元素，符合题目要求呀。

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution:def maxProfit(self, prices: List[int]) -> int:# minPrice维护prices[i]左侧的最小值# maxres维护prices[i]-minPrice的最大值res = 0minPrice = prices[0]for p in prices:res = max(res, p - minPrice)minPrice = min(minPrice, p)return res

在解决买卖股票求最大利润这一问题时，运用“枚举右，维护左”思路如下：
关键：

`minPrice 维护 prices[i] 左侧的最小值`

`maxres 维护 prices[i] - minPrice 的最大值`

1. 枚举右

从左到右依次遍历股票价格数组 prices，将每个价格视作可能的卖出价格，也就是在不断向右推进，考察每个位置上卖出股票的情况。

2. 维护左

用变量 minPrice 来维护当前位置左侧出现过的股票最低价格。在遍历过程中，每当遇到新的价格，就通过 min(minPrice, p) （p 为当前遍历到的价格）来更新 minPrice，保证它始终记录着左侧的最低价格。

3. 计算并更新最大利润

对于每个“枚举右”到的价格 p，计算 p - minPrice，这个差值代表以当前价格卖出能获得的利润，再通过 max(res, p - minPrice) 将其与已记录的最大利润 res 比较并取较大值更新 res。

经过这样一次遍历数组，不断“枚举右”并合理“维护左”的操作，最终 res 中就存储了整个股票价格序列中能获取的最大利润，以此高效地解决了该问题。

121. 买卖股票的最佳时机

from typing import Listclass Solution:def maxSum(self, nums: List[int]) -> int:num_dict = {}  # 哈希表，用于记录数位上最大数字对应的最大数max_sum = -1  # 初始化最大数对和为 -1，若不存在符合条件的数对则返回此值for num in nums:  # 枚举右，遍历数组numsmax_digit = int(max(str(num)))  # 获取当前数数位上最大数字if max_digit in num_dict:  # 如果该最大数位已在哈希表中有记录pair_sum = num + num_dict[max_digit]  # 计算当前数与哈希表中对应数的和max_sum = max(max_sum, pair_sum)  # 更新最大数对和# 更新哈希表中该最大数位对应的最大数，取当前数和原记录数的较大值num_dict[max_digit] = max(num, num_dict[max_digit])else:num_dict[max_digit] = num  # 将当前数作为该最大数位对应的数存入哈希表return max_sum

2815. 数组中的最大数对和

给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和最大的一对数，且这两个数数位上最大的数字相等。

返回最大和，如果不存在满足题意的数字对，返回 -1 。

from typing import Listclass Solution:def maxSum(self, nums: List[int]) -> int:num_dict = {}  # 哈希表，用于记录数位上最大数字对应的最大数max_sum = -1  # 初始化最大数对和为 -1，若不存在符合条件的数对则返回此值for num in nums:  # 枚举右，遍历数组numsmax_n = int(max(str(num)))  # 获取当前num的最大数位max_nif max_n in num_dict:       # 如果当前数位已经在num_dict出现，即num_dict[max_n]是上一个数对！pair_sum = num + num_dict[max_n]   # 当前max_sum = max(max_sum, pair_sum)# 当前num可能大于上一个哦！即num > num_dict[max_n]num_dict[max_n] = max(num, num_dict[max_n])else: # 如果没出现过当前数位max_n！num_dict[max_n] = numreturn max_sum

关键点在于不知道怎么得到最大数位…
max_n = int(max(str(num))) # 获取当前num的最大数位max_n
max_d = max(map(int, str(v)))这两个都可以！

2342. 数位和相等数对的最大和

这一题跟上一题差不多！

class Solution:def maximumSum(self, nums: List[int]) -> int:num_dict = {}    # 哈希表 用于 记录数位和max_sum = -1     # 当前最大和num_sum = 0for num in nums:    # 枚举右 遍历数组numsnum = str(num)num_sum = 0for x in num:num_sum += int(x)if num_sum in num_dict:pair_sum = int(num) + num_dict[num_sum]max_sum = max(max_sum, pair_sum)num_dict[num_sum] = max(int(num), num_dict[num_sum])else:num_dict[num_sum] = int(num)return max_sum

【枚举右，维护左】第一章（第1~7题）