Как найти два числа в массиве, которые вместе дадут заданную сумму? | Задача с JS собеседования

По условию входной массив имеет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Рассмотрим 2 варианта решения:
1) решение "в лоб", которое имеет сложность алгоритма O(n^2), оно самое простое, но не самое оптимальное;
2) оптимизованный алгоритм так, чтоб его сложность была линейная — O(n).

Свои варианты решений обязательно оставляйте в комментариях! С удовольствием и интересом все читаем.

В следующем видео мы разберем более сложную модификацию этой задачи — "Сумма трех чисел" (Sum of Three).

Подписывайтесь на канал и обязательно нажимайте на колокольчик, чтоб быть в курсе публикаций новых видео!

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

Присоединяйтесь к нам в соцсетях:

#javascript #задачи #leetcode #itсобеседование

[stormd]

Учитывая миллионные армии вайтишников, видео на этом канале незаслуженно имеют мало просмотров. Для новичков очень полезный канал. И автор позитивный, добрый и очень старается за качество видео. Спасибо, добрый человек!

[UtilitarHouse]

Хорошая задача. Здорово, что предлагается решение несколькими способами!

[kindsvater-]

мне надо было решить совсем другую задачу, но твоя помогла. Спасибо тебе, друх)

[katsiarynaramaniuk]

Спасибо за понятные объяснения и качественный контент

[TheSome]

При большом объёме однородных данных скорее всего наиболее эффективным окажется подход, в котором все значения сперва отсортируют (и отбросят значения, которые заведомо больше суммы даже без суммирования), а потом двумя указателями начнут сходиться к середине и тестировать сумму.

[SerzhNesteruk]

Можно решить и за один проход:
const sumOfTwo = (arr, target) => {
const lib = {};
for (let i = 0; i < arr.length; i++) {
const item = arr[i];
const diff = target - item;
if (diff in lib) {
return [lib[diff], i];
}
lib[item] = i;
}
return [];
};

[ЕвгенияОдесса-уи]

Спасибо, интересная задача. Можете разобрать : Есть некоторое целое число, найдите максимальное число, которое вы можете получить удалив ровно одну цифру заданного числа?

[exelione]

function twoSum(numbers, target) {
const res = {}
for (let i = 0; i < numbers.length; i++){

const comp = target - numbers[i]

if(res[comp]){
return [comp, numbers[i]]
}
res[numbers[i]]= true
}
}


export default twoSum

[FirstLast-hgyy]

@front-end Science Скажите пожалуйста, нужна ли математика что бы работать в фронтенде? а то смотрю название всех видео и страшно становиться)

[MikitaRashetnikau]

Можно и за один проход сделать, сложность правда так же самая по времени и по памяти

const sumOfTwo = (nums: number[], target: number) => {
const map = new Map();

for (let i = 0; i < nums.length; i++) {
const currentNum = nums[i];
const difference = target - currentNum;

if (map.has(difference)) {
return [map.get(difference), i]
}

map.set(currentNum, i)
}

return [];
}

[vaslsk]

Мое решение :

const sumOfTwo = (arr, target) => {
let result = arr.filter(x => arr.includes(target - x));
return result.length == 1 ? [] : result;
};
console.log(sumOfTwo([2, 7, 11, 15], 9));

Можно и до одной строки сократить, но будет плохо читаться. Код вроде простой и должен работать корректно при любых числах (вроде) :)

[romikonlinepotapenko]

Я бы сначала отфильтровал массив и убрал оттуда все числа которые больше target, а объект можно создать с помощью reduce:
const sumOfTwo = (arr, target) => {
arr = arr.filter(el => el < target);
const numObj = arr.reduce((a, c) => {
a[c] = arr.indexOf(c);
return a;
}, {});
for(let el of arr){
const diff = target - el;
if(numObj[diff] && numObj[diff] != arr.indexOf(el)) return [el, diff];
}
return [];
};

[EvilYou]

Получилось 2 решения, в общем-то такие же, как и в видео. Решение за O(n) никак не мог придумать, начал смотреть видео и как только Сергей сказал, что можно сделать через объект, я понял, как это сделать :)

Мои 2 варианта решения (для leetcode должны проходить лучше, так как в первом случае я не дожидаюсь конца прохода по двум циклам, и в обоих случаях не возвращаю ничего, если сумма не найдена (по условию, она будет найдена всегда)).
1) Сложность по времени: O (n^2), по памяти: O (1)
function twoSum(nums, target) {
if (nums.length === 2) return [0, 1];

for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
}
Runtime: 100 ms, faster than 56.44%
Memory Usage: 39.5 MB, less than 73.05%

2) Сложность по времени: O (n), по памяти O (n)
function twoSum(nums, target) {
if (nums.length === 2) return [0, 1];
let obj = {};

for (let i = 0; i < nums.length; i++) {
obj[nums[i]] = i;
}

for (let i = 0; i < nums.length; i++) {
let searchFor = target - nums[i];
if (obj[searchFor] && obj[searchFor] !== i) return [obj[searchFor], i];
}
}
Runtime: 68 ms, faster than 97.97%
Memory Usage: 41.8 MB, less than 8.24%

[nektosnext]

def sum_of_two(array, target):
for i in array:
for a in array:
if i + a == target:
return i, a

if __name__ == '__main__':
print(sum_of_two([2, 7, 11, 15], 13))
else:
print('this is the main file')

на питонсе потому что я искал другую задачу подсказки на кодварсе
а мне єта понрвилась и я решил

[mt]

Я бы еще на 11 строчку, на всякий случай, вместо проверки на flasy "numObject[diff]" сделал бы явкую проверку "numObject[diff] !== undefined". Если у нас в массиве с входными данными будет 0, то тут у нас может быть косяк.

P.S. я просто делал вариацию этой задачи, где возвращал не индксы, а сами числа.

[ArturchikTest]

Шо то меня сомненье гложет насчёт линейности. Ведь проверка есть ли элемент с таким ключом в объекте, по сути, не что иное как поиск в объекте ключа перебирая все элементы объекта. Да это быстрее чем цикл на JS, но всёравно это цикл в цикле и на больших числах будет заметно что нет никакой линейности.

[sdiana]

var twoSum = function(nums, target) {
const dict = new Map();

for(let i =0; i<nums.length; i++){
if(dict.has(target - nums[i])) return [dict.get(target - nums[i]), i];
else dict.set(nums[i], i);
}
};

[АндрейПушкарев-яы]

Второе решение заглохнет, если на вход придет массив типа [3, 3], а target будет 6

[true]

lst = list(map(int, input().split()))
total = int(input())
def sum_of_two(lst, total):
for i in lst:
for j in lst:
if i + j == total and i != j:
return f"{i} {j}"
return None

print(sum_of_two(lst, total))
Если будет 2 одинаковых числа выводит None

[artaksafaryan]

const item = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
if(arr[i] + arr[i - 1] === val){
return true;
}
}

return false;
}

console.log(item([2, 7, 8, 9, 11], 20));