Массивы: два указателя и скользящее окно

def pair_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        print(f"  left={left} ({nums[left]}), right={right} ({nums[right]}), сумма={s}")
        if s == target:
            return left, right
        if s < target:
            left += 1          # сумма мала → нужен больший элемент слева
        else:
            right -= 1         # сумма велика → нужен меньший элемент справа
    return None

print(pair_sum_sorted([1, 3, 4, 6, 8, 11], 10))

def remove_duplicates(nums):
    """Удалить дубликаты из отсортированного списка на месте, вернуть новую длину."""
    if not nums:
        return 0
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow - 1]:      # новый уникальный элемент
            nums[slow] = nums[fast]
            slow += 1
    return slow

data = [1, 1, 2, 2, 2, 3, 5, 5]
k = remove_duplicates(data)
print(k, data[:k])

def max_average(nums, k):
    window = sum(nums[:k])                 # первое окно — O(k)
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]    # вошёл новый, вышел старый — O(1)
        best = max(best, window)
    return best / k

print(max_average([1, 12, -5, -6, 50, 3], 4))

from collections import Counter

def min_window_with_sum(nums, target):
    """Длина кратчайшего подмассива с суммой >= target (числа положительные)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:             # окно валидно — пробуем сжать
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(min_window_with_sum([2, 3, 1, 2, 4, 3], 7))     # [4, 3] → 2

def longest_with_k_distinct(s, k):
    """Самая длинная подстрока, где не больше k разных символов."""
    counts = Counter()
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_with_k_distinct("eceba", 2))            # "ece" → 3

from itertools import accumulate

nums = [3, -1, 4, 1, 5, 9, -2, 6]
prefix = [0] + list(accumulate(nums))
print(prefix)

def range_sum(l, r):            # сумма nums[l:r]
    return prefix[r] - prefix[l]

print(range_sum(2, 5), sum(nums[2:5]))

def count_subarrays_with_sum(nums, k):
    """Сколько подмассивов имеют сумму k (числа любого знака) — префиксы + словарь, O(n)."""
    seen = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)     # есть ли префикс, дающий отрезок с суммой k
        seen[total] = seen.get(total, 0) + 1
    return count

print(count_subarrays_with_sum([1, 1, 1], 2), count_subarrays_with_sum([1, 2, 3, -3, 3], 3))