1. Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index₁ must be less than index₂. Please note that your returned answers (both index₁ and index₂) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers = {2, 7, 11, 15}, target = 9

Output: index₁ = 1, index₂ = 2

1. Две суммы

Задан массив целых чисел. Найдите два числа, сумма которых равна заданному числу.

Функция twoSum должна вернуть индексы таких двух чисел, сумма которых равна target, где index₁ должен быть меньше index₂. Возвращаемые значения (и index₁ и index₂) должны быть ненулевыми.

Считайте, что для заданных входных данных имеется в точности одно решение.

Вход: numbers = {2, 7, 11, 15}, target = 9

Выход: index₁ = 1, index₂ = 2

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

}

};

РЕШЕНИЕ

последовательности

Анализ алгоритма

Можно воспользоваться двумя циклами, перебрав все пары индексов. Получим решение за O(n²).

Рассмотрим массив структур из двух элементов – вместе с числами будем хранить их индексы в исходном масиве. Отсортируем его. Далее воспользуемся двумя указателями, двигающимися с краев внутрь. За O(nlog₂n) задача будет решена.

Реализация алгоритма

class Solution

{

public:

vector<int> twoSum(vector<int> &numbers, int target)

{

vector<int> res;

vector<pair<int,int> > num;

Создаем массив с числами и соответствующими индексами.

for(int i = 0; i < numbers.size(); i++)

num.push_back(make_pair(numbers[i],i+1));

Сортируем массив.

sort(num.begin(),num.end());

Инициализируем указатели: i устанавливаем на начало массива (нулевой элемент), j на конец массива (последний элемент).

int i = 0, j = num.size() - 1;

while(i < j)

{

Если сумма чисел, на которые указывают i и j, равна target, то искомая пара чисел найдена. Создаем и сортируем пару индексов.

if (num[i].first + num[j].first == target)

{

res.push_back(num[i].second);

res.push_back(num[j].second);

sort(res.begin(),res.end());

return res;

}

Если сумма меньше target, то двигаем вправо левый указатель. Если сумма больше target, то двигаем влево правый указатель.

else if (num[i].first + num[j].first < target) i++; else j--;

}

return res;

}

};