零、常用枚举技巧

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. 1010. 总持续时间可被 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 个键。