В этой статье блога мы углубимся в различные методы поиска пары в массиве с заданной суммой, используя концепцию хеширования. Мы рассмотрим несколько подходов, обсудим их плюсы и минусы и предоставим примеры кода для демонстрации их реализации. Давайте погрузимся!

Метод 1: подход грубой силы
Подход грубой силы включает в себя проверку каждой возможной пары элементов в массиве и сравнение их суммы с целевой суммой. Хотя этот метод прост, его временная сложность равна O(n^2), что делает его неэффективным для больших массивов.

def find_pair_brute_force(arr, target_sum):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target_sum:
                return (arr[i], arr[j])
    return None

Метод 2: использование хеш-набора
В этом подходе мы используем хеш-набор для хранения разницы между целевой суммой и текущим элементом при обходе массива. Если мы встретим элемент, который уже присутствует в хеш-наборе, это означает, что мы нашли пару с нужной суммой.

def find_pair_hash_set(arr, target_sum):
    hash_set = set()
    for num in arr:
        if target_sum - num in hash_set:
            return (target_sum - num, num)
        hash_set.add(num)
    return None

Метод 3: сортировка и два указателя
Этот метод включает в себя сортировку массива в порядке возрастания и использование двух указателей: один начинается с начала, другой — с конца. Сравнивая сумму указанных элементов с целевой суммой, мы можем соответствующим образом перемещать указатели.

def find_pair_sorting(arr, target_sum):
    arr.sort()
    left = 0
    right = len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target_sum:
            return (arr[left], arr[right])
        elif current_sum < target_sum:
            left += 1
        else:
            right -= 1
    return None

Метод 4: использование хэш-карты
В этом подходе мы используем хеш-карту для хранения частоты каждого элемента в массиве. Обходя массив, мы вычисляем разницу между целевой суммой и текущим элементом. Если эта разница существует в хеш-карте и ее частота больше нуля, мы нашли действительную пару.

def find_pair_hash_map(arr, target_sum):
    freq_map = {}
    for num in arr:
        freq_map[num] = freq_map.get(num, 0) + 1
    for num in arr:
        complement = target_sum - num
        if complement in freq_map and freq_map[complement] > 0:
            return (num, complement)
    return None

Мы исследовали несколько методов поиска пары в массиве с заданной суммой с помощью хеширования. Каждый подход имеет свои преимущества и недостатки с точки зрения временной сложности и сложности реализации. Выбор метода зависит от конкретных требований решаемой задачи. Используя эти методы, вы можете эффективно решать аналогичные алгоритмические задачи, связанные с массивами и суммами.