0.1 枚举右，维护左

提示

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

我把这个技巧叫做 枚举右，维护左。

提示

阿囧：本质是用空间维护遍历过的数组左边元素状态，从而达到只用遍历一次数组求解的效果

1. 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)，哈希表空间换时间

2. 1512. 好数对的数目

   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)，哈希表空间换时间

3. 219. 存在重复元素 II

   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)，哈希表空间换时间

4. 121. 买卖股票的最佳时机

   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)，只用到若干常量

5. 2815. 数组中的最大数对和

   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：没有必要，不同底数之间只有常系数的差别。

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

   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

7. 1679. K 和数对的最大数目

   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)

8. 2260. 必须拿起的最小连续卡牌数

   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)

9. 1010. 总持续时间可被 60 整除的歌曲

   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 个键。

10. 3185. 构成整天的下标对数目 II

    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 个键。

11. 2748. 美丽下标对的数目

    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)

12. 2874. 有序三元组中的最大值 II

    要找(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)

    (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)