Хеш-таблицы в задачах

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

print(contains_duplicate([1, 2, 3, 1]), contains_duplicate([1, 2, 3]))
print(len(set([1, 2, 3, 1])) != len([1, 2, 3, 1]))    # то же одной строкой

def two_sum(nums, target):
    index = {}                                    # значение → индекс
    for i, x in enumerate(nums):
        need = target - x
        print(f"  i={i}, x={x}, ищем {need}, словарь={index}")
        if need in index:
            return [index[need], i]
        index[x] = i

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)              # O(n); sorted(a) == sorted(b) — O(n log n)

print(is_anagram("listen", "silent"), is_anagram("rat", "car"))

def can_build(note, magazine):
    """Можно ли составить записку из букв журнала (каждая буква — один раз)."""
    need, have = Counter(note), Counter(magazine)
    return all(have[ch] >= cnt for ch, cnt in need.items())   # или: not (need - have)

print(can_build("aab", "baa"), can_build("aa", "ab"))

def top_k_frequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))                 # у анаграмм одинаковый отсортированный вид
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def group_by_shift(words):
    """Строки, получаемые друг из друга сдвигом букв: abc, bcd, xyz."""
    groups = defaultdict(list)
    for w in words:
        key = tuple((ord(c) - ord(w[0])) % 26 for c in w)    # разности между буквами
        groups[key].append(w)
    return list(groups.values())

print(group_by_shift(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]))

def longest_balanced(bits):
    """Самый длинный подмассив с равным числом 0 и 1."""
    first_index = {0: -1}                       # баланс → первая позиция
    balance = best = 0
    for i, b in enumerate(bits):
        balance += 1 if b == 1 else -1
        if balance in first_index:
            best = max(best, i - first_index[balance])
        else:
            first_index[balance] = i
    return best

print(longest_balanced([0, 1, 0, 0, 1, 1, 0]))

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:                 # начало цепочки
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)              # недавно использован
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)       # вытеснить самый старый

cache = LRUCache(2)
cache.put(1, "a"); cache.put(2, "b")
print(cache.get(1))          # a — теперь 1 свежий
cache.put(3, "c")            # вытеснит 2
print(cache.get(2), cache.get(3), list(cache.data))