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

Методы:

1. Метод грубой силы:
   Подход грубой силы включает в себя проверку каждой возможной пары в массиве и сравнение их суммы с заданным целевым значением. Вот пример кода на Python:

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
# Example usage
array = [2, 4, 6, 8, 10]
target = 14
result = find_pair_brute_force(array, target)
print(result)  # Output: (4, 10)

2. Метод сортировки и двух указателей.
   Этот метод использует тот факт, что массив сортируется, что снижает временную сложность. Мы используем два указателя, один из которых начинается с начала, а другой с конца, и перемещаем их навстречу друг другу на основе сравнения с целевой суммой. Вот пример на Python:

def find_pair_sorted_array(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
# Example usage
array = [2, 4, 6, 8, 10]
target = 14
result = find_pair_sorted_array(array, target)
print(result)  # Output: (4, 10)

3. Метод хеширования.
   Метод хеширования использует хеш-таблицу (словарь) для хранения разницы между целевой суммой и элементами массива. Перебирая массив, мы проверяем, существует ли дополнение текущего элемента в хеш-таблице. Вот пример на Python:

def find_pair_hashing(arr, target_sum):
    complement_dict = {}
    for num in arr:
        complement = target_sum - num
        if complement in complement_dict:
            return complement, num
        complement_dict[num] = True
    return None
# Example usage
array = [2, 4, 6, 8, 10]
target = 14
result = find_pair_hashing(array, target)
print(result)  # Output: (4, 10)

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