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

Метод 1: подход грубой силы
Подход грубой силы — это самый простой метод решения проблемы двух сумм. Он включает в себя вложенные циклы, которые перебирают массив для проверки всех возможных пар чисел. Вот фрагмент кода C++ для этого подхода:

#include <vector>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {}; // No solution found
}

Метод 2: использование хэш-карты
Другой эффективный подход к решению проблемы двух сумм включает использование хеш-карты (unordered_map в C++). Мы будем перебирать массив, сохраняя индекс каждого числа в хеш-карте. Во время итерации мы также проверим, существует ли дополнение текущего числа (цель минус текущее число) в хеш-карте. Вот фрагмент кода C++ для этого подхода:

#include <vector>
#include <unordered_map>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {}; // No solution found
}

Метод 3: сортировка и два указателя
Если массив отсортирован, мы можем использовать метод двух указателей для эффективного решения проблемы двух сумм. Мы будем поддерживать два указателя: один в начале, а другой в конце массива. Сравнивая сумму указанных элементов с целью, мы можем сузить поиск. Вот фрагмент кода C++ для этого подхода:

#include <vector>
#include <algorithm>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};
        }
        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {}; // No solution found
}

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