Пары чисел с заданной суммой

Решение

Задача требует найти все пары чисел в массиве, чья сумма равна целевому значению. Это фундаментальная задача, которая требует выбора оптимального подхода в зависимости от требований.

Решение 1: Хеш-таблица (Оптимальное для больших данных)

Используем HashSet для отслеживания уже посещённых элементов. Это позволяет находить все пары за один проход.

def find_pairs_hashmap(arr: list[int], target_sum: int) -> list[tuple[int, int]]:
    """
    Находит все пары чисел с заданной суммой используя хеш-таблицу.
    
    Args:
        arr: Массив целых чисел
        target_sum: Целевая сумма
    
    Returns:
        Список всех пар чисел, сумма которых равна target_sum
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    pairs = []
    seen = set()
    
    for num in arr:
        complement = target_sum - num
        
        if complement in seen:
            pairs.append((complement, num))
        
        seen.add(num)
    
    return pairs

Решение 2: Сортировка + Двуатоки (Two-Pointer)

Если нужна отсортированная последовательность пар или требуется определённый порядок.

def find_pairs_two_pointer(arr: list[int], target_sum: int) -> list[tuple[int, int]]:
    """
    Находит все пары чисел с заданной суммой используя два указателя.
    
    Args:
        arr: Массив целых чисел
        target_sum: Целевая сумма
    
    Returns:
        Список всех пар чисел, сумма которых равна target_sum
    
    Time Complexity: O(n log n) из-за сортировки
    Space Complexity: O(1) не считая результата
    """
    sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])
    pairs = []
    left, right = 0, len(sorted_arr) - 1
    
    while left < right:
        current_sum = sorted_arr[left][1] + sorted_arr[right][1]
        
        if current_sum == target_sum:
            pairs.append((sorted_arr[left][1], sorted_arr[right][1]))
            left += 1
            right -= 1
        elif current_sum < target_sum:
            left += 1
        else:
            right -= 1
    
    return pairs

Примеры использования

# Пример из условия
arr = [1, 5, 7, -1, 5]
target_sum = 6

result1 = find_pairs_hashmap(arr, target_sum)
print(result1)  # [(1, 5), (7, -1), (1, 5)]

result2 = find_pairs_two_pointer(arr, target_sum)
print(result2)  # [(1, 5), (7, -1), (1, 5)]

# Массив с дубликатами
arr2 = [2, 2, 2, 2]
print(find_pairs_hashmap(arr2, 4))  # [(2, 2), (2, 2), (2, 2)]

# Пустой результат
arr3 = [1, 2, 3]
print(find_pairs_hashmap(arr3, 10))  # []

# Отрицательные числа
arr4 = [-5, -3, 0, 3, 5]
print(find_pairs_hashmap(arr4, 0))  # [(-5, 5), (-3, 3)]

Решение 3: Уникальные пары (без дубликатов)

Если нужны только уникальные пары без учёта порядка:

def find_unique_pairs(arr: list[int], target_sum: int) -> list[tuple[int, int]]:
    """
    Находит уникальные пары без дубликатов.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    pairs_set = set()
    seen = set()
    
    for num in arr:
        complement = target_sum - num
        
        if complement in seen:
            # Сортируем пару для избежания дубликатов (1,5) и (5,1)
            pair = tuple(sorted([complement, num]))
            pairs_set.add(pair)
        
        seen.add(num)
    
    return list(pairs_set)

# Использование
arr = [1, 5, 7, -1, 5]
print(find_unique_pairs(arr, 6))  # [(1, 5), (-1, 7)]

Анализ сложности

Для QA тестирования

При тестировании алгоритма проверьте граничные случаи:

• Пустой массив
• Массив с одним элементом
• Отрицательные числа
• Нулевые значения
• Дубликаты в массиве
• Массив где нет подходящих пар
• Большие значения (переполнение?)