Arrays and Hashing

1. Contains Duplicate

# 1.3. Хеш-множество (оптимальное решение): Time O(n), Space O(n)
def ContainsDuplicate3(self, nums: List[int]) -> bool:
    s = set()
    for n in nums:
        if n in s:
            return True
        s.add(n)
    return False

2. Valid Anagram

# 2.1. Сортировка (оптимальное решение): Time O(n log n + m log m), Space O(1) или O(n+m)
def ValidAnagram1(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

3. Two Sum

# 3.4. Хеш-таблица (за один проход) (оптимальный вариант): Time O(n), Space O(n)
def TwoSum4(self, nums: List[int], target: int) -> List[int]:
    prevEl = {}
    for i, n in enumerate(nums):
        diff = target - n
        if diff in prevEl:
            return [prevEl[diff], i]
        prevEl[n] = i
    return []

4. Group Anagrams

# # 2. Хеш-таблица (оптимальный вариант): Time O(m * n), Space O(m * n)
def GroupAnagrams2(self, strs: List[str]) -> List[List[str]]:
    # чтобы значения по ключам не перезатирались, надо создать словарь ключ - список.
    # сопоставляем количество символов в каждой строке с набором анограм
    anagramsMap = defaultdict(list)
    for s in strs:
        # обычные словари с подсчетом количества букв тут не получится, потому что далее идет перевод в кортеж
        mass = [0] * 26
        for e in s:
            mass[ord(e) - ord('a')] += 1
        # в python списки не могут быть ключами, поэтому для ключей надо сделать хешируемый кортеж (неизменяемый список)
        anagramsMap[tuple(mass)].append(s)
    return list(anagramsMap.values())