数组和哈希

217 包含重复元素

设 nums 列表中元素的数量为 n。

时间复杂度： 我们遍历列表一次。每个成员检查 (i 在 counter 中) 和将元素插入集合的平均时间复杂度为 O(1)。在最坏情况下（所有元素都不同）我们执行这些操作 n 次，从而达到 O(n) 的时间复杂度。

空间复杂度： 额外的空间来自集合 counter。在最坏情况下（所有元素都不同），集合存储所有 n 个元素，因此空间复杂度为 O(n)。

#217
from typing import List

def containsDuplicate(nums: List[int]) -> bool:
    counter = set()
    for num in nums:
      if num in counter:
        return True
      counter.add(num)
    return False

#include <vector>
#include <unordered_set>

bool containsDuplicate(std::vector<int>& nums){
  std::unordered_set<int> memo = {};

  for(auto num: nums){
    if(memo.find(num) != memo.end()){
      return true;
    }
    memo.insert(num);
  }

  return false;
};

242 有效的字母异位词

时间复杂度：我们比较 s 和 t 的长度。这需要 O(1) 时间。如果长度不同，则字符串不是字母异位词。如果长度相等，则设公共长度为 n。我们一次遍历两个字符串，以构建两个哈希表，用于统计每个字符的频率。这需要 O(n) 时间。在最坏情况下，比较这两个哈希表也需要 O(n) 时间。总时间复杂度为 O(n)。

空间复杂度：额外的空间来自用于存储字符频率的两个哈希表。在最坏情况下，每个字符串中的每个字符都是唯一的，因此哈希表存储最多 n 个条目。由于我们在计算之前确保字符串长度相等，因此空间复杂度为 O(n)。

def isAnagram(s: str, t:str) -> bool:

  if len(s) != len(t):
    return False
  
  s_map, t_map = {}, {}

  for i in range(len(s)):
    s_map[s[i]] = 1 + s_map.get(s[i], 0)
    t_map[t[i]] = 1 + t_map.get(t[i], 0)

  return s_map == t_map

bool isAnagram(std::string s, std::string t){
  if(s.length() != t.length()){
    return false;
  }

  std::unordered_map<char, int> countS;
  std::unordered_map<char, int> countT;
  for(int i = 0; i < s.length(); i++){
    countS[s[i]]++;
    countT[t[i]]++;
  }

  return countS == countT; 
};

bool isAnagram(std::string s, std::string t){
  if(s.length() != t.length()){
    return false;
  }

  std::vector<int> count(26, 0);

  for(int i = 0; i < s.length(); i++){
    count[s[i] - 'a']++;
    count[t[i] - 'a']--; 
  }

  for(int i: count){
    if(i != 0)
      return false;
  }

  return true;
};

1 两数之和

设 nums 列表中元素的数量为 n。

时间复杂度：我们遍历列表一次。对于每个元素，我们计算 target - num 并检查当前数字是否已经作为所需的差值被见过。字典的查找和插入的平均时间复杂度为 O(1)，因此总时间复杂度为 O(n)。

空间复杂度：额外的空间来自用于存储先前见过的差值及其索引的字典。在最坏情况下（未找到解决方案直到最后），字典存储最多 n 个条目，从而实现 O(n) 的空间复杂度。

def twoSum(nums: List[int], target: int) -> List[int]:
  diffs = {}
  for idx, num in enumerate(nums):
    diff = target - num
    if num in diffs:
      return [diffs[diff], idx]
    diffs[diff] = idx

49 组Anagrams

设 strs 列表中字符串的数量为 n，设 k 为字符串的最大长度。

时间复杂度： 我们遍历字符串列表一次，这需要 O(n) 时间。 对于每个字符串，我们对其字符进行排序以生成键。对长度为 k 的字符串进行排序需要 O(k log k) 时间。 因此，总时间复杂度为 O(n * k * log(k))。 将哈希表的键转换为列表需要 O(n) 时间，这不会改变总复杂度。 总时间复杂度为 O(n * klog(k))

空间复杂度: 我们使用哈希表将字符串按其排序后的字符键进行分组。在最坏的情况下，所有字符串都是唯一的，并且每个都形成自己的组。用于存储组和键的总额外空间为 O(n · k)，其中 n 是 str 中字符串的数量，k 是最长字符串的长度。

from typing import List
from collections import defaultdict


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    res = defaultdict(list)

    for word in strs:
        key = "".join(sorted(word))
        res[key].append(word)
    return list(res.values())

347 Top K Frequent Elements

from collections import defaultdict


def topKFrequent(nums: List[int], k: int) -> List[int]:
  memo = defaultdict(int)
  for num in nums:
    memo[num] += 1
  
  sorted_dict = sorted(memo.items(), key=lambda item: item[1], reverse=True)

  return [item[0] for item in sorted_dict[:k]]

?Encode and Decode Strings

def encode(strs: List[str]) -> str:
  for idx in range(len(strs)):
    strs[idx] = f"{str(len(strs[idx]))}#{strs[idx]}"
  return "".join(strs)
     
def decode(s: str) -> List[str]:
  res = []
  r = 0
  while r < len(s):
    l = r
    while s[r] != "#":
      r += 1
    
    length = int(s[l:r])
    l = r + 1
    r = l + length

    res.append(s[l:r])
  
  return res

238 Product of Array Except Self

import copy

def productExceptSelf(nums: List[int]) -> List[int]:
  forward = copy.deepcopy(nums)
  backward = copy.deepcopy(nums)

  for i in range(1, len(nums)):
    forward[i] *= forward[i - 1] 
    backward[-i - 1] *= backward[-i]
  
  forward = forward[:-1]
  backward = backward[1:]
  
  for i in range(1, len(backward)):
    backward[i] *= forward[i - 1]
  
  backward.append(forward[-1])
  return backward

36 有效的 Sudoku

时间复杂度：O(n²)。我们扫描棋盘上的每个单元格，每次扫描时间为 n × n。对于每个填充单元格，我们执行常量数量的哈希集查找和插入（行、列和 3×3 块），每次平均时间为 O(1)。

空间复杂度：O(n²)。在最坏情况下，我们可能存储每个 n 行、n 列和 n 个子块的最多 n 个值。这仍然是 O(n²)（忽略常数）。

def isValidSudoku(board: List[List[str]]) -> bool:
  rows_memo = defaultdict(set)
  cols_memo = defaultdict(set)
  squares_memo = defaultdict(set)

  for row_num, row in enumerate(board):
    for col_num, elem in enumerate(row):
      if elem == '.':
        continue

      if elem in rows_memo[row_num]:
        return False
      else:
        rows_memo[row_num].add(elem)
      
      if elem in cols_memo[col_num]:
        return False
      else:
        cols_memo[col_num].add(elem)
      
      if elem in squares_memo[(row_num // 3, col_num // 3)]:
        return False
      else:
        squares_memo[(row_num // 3, col_num // 3)].add(elem)
      
  return True

128 最长连续序列

设 nums 列表中元素的数量为 n。

时间复杂度：O(n)。将列表转换为集合需要 O(n) 时间，检查每个元素需要 O(n) 时间。

空间复杂度：O(n)。用于将 nums 列表转换为集合的唯一额外空间，最多需要 O(n) 空间。

def longestConsecutive(nums: List[int]) -> int:
  nums_set = set(nums)

  # The first term of the sequence should not have any adjacent term that is smaller than it.
  # If 5 is the start of a sequence, 4 should not exist or else 5 would not be the start of the sequence
  # We can check only the start of a sequence and record the longest sequence
  
  res = 0
  for num in nums_set:
    if num - 1 in nums_set:
      continue
    else:
      count = 1
      while num + 1 in nums_set:
        count += 1
        num += 1
      res = res if res > count else count
  return res