8.0 常用枚举技巧
0.1 枚举右，维护左
提示
阿囧：本质是用空间维护遍历过的数组左边元素状态，从而达到只用遍历一次数组求解的效果
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for j, num in enumerate(nums): find = target - num if find in dic: return [dic[find], j] else: dic[num] = j时间复杂度：O(n)
空间复杂度：O(n)，哈希表空间换时间
class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: cnt = defaultdict(int) res = 0 for num in nums: res += cnt[num] cnt[num] += 1 return res时间复杂度：O(n)
空间复杂度：O(n)，哈希表空间换时间
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: dic = {} for j, num in enumerate(nums): if num in dic.keys() and j - dic[num] <= k: return True dic[num] = j return False时间复杂度：O(n)
空间复杂度：O(n)，哈希表空间换时间
class Solution: def maxProfit(self, prices: List[int]) -> int: res = 0 min_pric, max_price = prices[0], prices[0] for price in prices: if price < min_pric: min_pric = price max_price = price # 如果买入，那么只能在 price 后面卖出 if price > max_price: max_price = price res = max(res, max_price - min_pric) # 记录最大收入 return res时间复杂度：O(n)
空间复杂度：O(1)，只用到若干常量
class Solution: def maxSum(self, nums: List[int]) -> int: help = [0] * 10 # 只有 0~9 的数字类型 res = -1 for num in nums: index = int(max(str(num))) if help[index]: res = max(res, help[index] + num) if num > help[index]: help[index] = num return res时间复杂度：O(nlogU)，其中 n 为 nums 的长度，U = max(nums)
空间复杂度：O(1)，只用到若干常量
Q：这个算法复杂度中的 log 的底数是10，而常见的一般是 2，所以有没有标明一下的必要呢？
A：没有必要，不同底数之间只有常系数的差别。
class Solution: def maximumSum(self, nums: List[int]) -> int: dic = defaultdict(int) res = -1 def num_sum(num): # 求数位和 if num // 10 == 0: return num else: return num % 10 + num_sum(num // 10) for num in nums: key = num_sum(num) if dic[key]: res = max(res, dic[key] + num) if num > dic[key]: dic[key] = num return res时间复杂度：O(nlogU)，其中 n 为 nums 的长度，U = max(nums)
空间复杂度：O(DlogU)，其中 D = 9
class Solution: def maxOperations(self, nums: List[int], k: int) -> int: dic = defaultdict(int) res = 0 for num in nums: if dic[num]: res += 1 dic[num] -= 1 else: dic[k - num] += 1 return res时间复杂度：O(n)，其中 n 为 nums 的长度
空间复杂度：O(n)
class Solution: def minimumCardPickup(self, cards: List[int]) -> int: res = 10e5 + 1 dic = {} for j, card in enumerate(cards): if card in dic: res = min(res, j - dic[card] + 1) dic[card] = j return -1 if res == 10e5 + 1 else res时间复杂度：O(n)，其中 n 为 cards 的长度
空间复杂度：O(n)
class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: dic = defaultdict(int) res = 0 for j, t in enumerate(time): t = t % 60 if t == 0: res += dic[0] res += dic[60 - t] dic[t] += 1 return res时间复杂度：O(n)，其中 n 为 time 的长度
空间复杂度：O(1)，由于字典 dic 中最多只有 60 个键。
class Solution: def countCompleteDayPairs(self, hours: List[int]) -> int: res = 0 dic = defaultdict(int) for hour in hours: hour = hour % 24 res += dic[24 - hour] if hour == 0: res += dic[0] dic[hour] += 1 return res时间复杂度：O(n)，其中 n 为 hours 的长度
空间复杂度：O(1)，由于字典 dic 中最多只有 24 个键。
class Solution: def countBeautifulPairs(self, nums: List[int]) -> int: cnt = [0] * 10 # 统计首位为 1~9 的数字个数 res = 0 for num in nums: for i in range(1, 10): if gcd(num % 10, i) == 1: res += cnt[i] while num >= 10: num //= 10 cnt[num] += 1 return res时间复杂度：O(n)，其中 n 为 nums 的长度
空间复杂度：O(1)
思路1：要找
(nums[i] - nums[j]) * nums[k]的最大值，可以枚举j，维护j左边最大值和右边最大值class Solution: def maximumTripletValue(self, nums: List[int]) -> int: n = len(nums) suf_max = [0] * (n + 1) for i in range(n - 1, 1, -1): suf_max[i] = max(suf_max[i + 1], nums[i]) ans = pre_max = 0 for j, x in enumerate(nums): ans = max(ans, (pre_max - x) * suf_max[j + 1]) pre_max = max(pre_max, x) return ans时间复杂度：O(n)，其中 n 为 nums 的长度。
空间复杂度：O(n)
思路2：
(nums[i] - nums[j]) * nums[k]的最大值，可以枚举k，维护k左边最大差值class Solution: def maximumTripletValue(self, nums: List[int]) -> int: pre_max = 0 max_diff = 0 res = 0 for num in nums: res = max(res, max_diff * num) max_diff = max(max_diff, pre_max - num) pre_max = max(pre_max, num) return res时间复杂度：O(n)，其中 n 为 nums 的长度。
空间复杂度：O(1)
思路：要找
v[i] + v[j] + i - j的最大值，可以变形成(vi + i) + (vj - j)，枚举 j，保存左边的最大值left_max，比较left_max和当前j的总体值class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int: # [8,2,0,0,0] # [0,0,3,-1,2] res = 0 left_max = float('-inf') for j, v in enumerate(values): res = max(res, left_max + v - j) left_max = max(left_max, v + j) return res时间复杂度：O(n)，其中 n 为 values 的长度。
空间复杂度：O(1)
思路：要找
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])，可以变形成nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，遍历一遍nums，用cnt统计值相等的数量（假设有5个，能组成 对）提示
最后取余不能使用
10e9 + 7，这是浮点数，会产生误差，应该使用整数常量10**9 + 7class Solution: def countNicePairs(self, nums: List[int]) -> int: def rev(x): y = 0 while x: y = y * 10 + x % 10 x //= 10 return y cnt = Counter(num - rev(num) for num in nums) return sum(v * (v - 1) // 2 for v in cnt.values()) % (10**9 + 7)时间复杂度：O(nlogM)，其中 n 和 M 分别是数组 nums 的长度和数组 nums 中的最大值
空间复杂度：O(n)
0.2 枚举中间
对于三个或者四个变量的问题，枚举中间的变量往往更好算。
思路：要三者和最小，可以先找山头（固定），再找两边最小的，但是山头不知道后面的谁最小，因此可以先从后往前遍历得到后缀最小值
suf，再从前往后遍历class Solution: def minimumSum(self, nums: List[int]) -> int: left_min = nums[0] n = len(nums) suf = [0] * n suf[-1] = nums[-1] for j in range(n - 2, -1, -1): suf[j] = min(suf[j + 1], nums[j]) pre = nums[0] res = float('inf') for i in range(1, n - 1): if pre < nums[i] > suf[i + 1]: res = min(res, pre + nums[i] + suf[i + 1]) pre = min(pre, nums[i]) return -1 if res == inf else res时间复杂度：O(n)，其中 n 为 nums 的长度。
空间复杂度：O(n)