найти два элемента, поэтому сумма равна заданному значению

Question

Даны два набора чисел «n». A и B. Выберите один элемент из A и один из B, чтобы сумма была равна заданному значению «val».

Я получил решение как:

Мы можем хэширования элементов множества A и Set B и проверить для каждого элемента в множестве А существует ли вал-обр [я] в хэш Set B или нет. Это займет время O (n) и O (n) Могут ли быть лучшие решения с пространством как O (1) и время O (n)?

Answer 1

Поскольку у вас есть оба массива, которые НЕ отсортированы, у вас нет НИКАКИХ других вариантов, но смотрите на каждый элемент один за другим. Таким образом, вы не можете получить ниже O(n) времени работы. Я думаю, что подход, который вы используете, в порядке.

Читайте эти родственные сообщения:

Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

Find two elements in an array that sum to k