Сумма двух значений

Постановка задачи

Учитывая массив целых чисел и значение, определите, есть ли в массиве какие-либо два целых числа, сумма которых равна заданному значению. Вернуть true, если сумма существует, и false, если нет.

Рассмотрим этот массив и целевые суммы:

Подсказки

  • Использовать хеширование
  • Использовать сравнение между элементами

Попробуйте сами

  • путь> C ++
  • C ++
  • путь> C ++
  • Java
  • Java
  • Python
  • Python
  • путь> JavaScript
  • JavaScript
  • Ruby
  • Ruby
 bool find_sum_of_two (vector  & A, int val) {//TODO: Write - Your - Code return false;} 

Решение

  • C ++
  • путь> C++
  • C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 bool find_sum_of_two (vector  & A, int val) {unordered_set  found_values;  for (int & a: A) {if (found_values.find (val - a)! = found_values.end ()) {return true;  } found_values. вставить (а);  } return false;} int main () {вектор  v = {5, 7, 1, 2, 8, 4, 3};  вектор  test = {3, 20, 1, 2, 7};  for (int i = 0; i  

Решение Объяснение

Сложность времени выполнения

Сложность выполнения этого решения линейна, O (n).

Сложность памяти

Сложность памяти этого решения линейна, O (n).

Разбор решения

В этом решении вы можете использовать следующий алгоритм для поиска пары, которая в сумме соответствует цели (скажем, val ).

  • Просканируйте весь массив один раз и сохраните посещенные элементы в хеш-наборе.
  • Во время сканирования для каждого элемента e в массиве мы проверяем, val e присутствует в наборе хешей, т.е. val e уже посещен.
    • Если val e находится в наборе хешей, это означает, что есть пара ( e , val e ) в массиве, сумма которого равна заданному val .
    • Если мы исчерпали все элементы в массиве и не нашли ни одного такая пара, функция вернет false.
Оцените статью
nanomode.ru
Добавить комментарий