How to find two numbers in array that together will give a desired sum? | Sum of Two | JS
ฝัง
- เผยแพร่เมื่อ 3 ต.ค. 2024
- В этом видео мы рассмотрим решение задачи, о которой вы писали в комментариях - "Сумма двух чисел" (Sum of Two). Уровень задачи на Leetcode - easy: leetcode.com/p... Условия задачи: дан массив с числами, в нем необходимо найти индексы двух чисел, сумма которых будет равна заданному числу N.
По условию входной массив имеет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Рассмотрим 2 варианта решения:
1) решение "в лоб", которое имеет сложность алгоритма O(n^2), оно самое простое, но не самое оптимальное;
2) оптимизованный алгоритм так, чтоб его сложность была линейная - O(n).
Свои варианты решений обязательно оставляйте в комментариях! С удовольствием и интересом все читаем.
Код на решение из видео: codepen.io/puz...
В следующем видео мы разберем более сложную модификацию этой задачи - "Сумма трех чисел" (Sum of Three).
Подписывайтесь на канал и обязательно нажимайте на колокольчик, чтоб быть в курсе публикаций новых видео!
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-scienc...
#javascript #задачи #leetcode #itсобеседование
Учитывая миллионные армии вайтишников, видео на этом канале незаслуженно имеют мало просмотров. Для новичков очень полезный канал. И автор позитивный, добрый и очень старается за качество видео. Спасибо, добрый человек!
Спасибо за поддержку! Очень ценно для нас!
Да какие миллионные армии я вас умоляю. У абсолютного большинства людей от подобных видео только голова разболится и они пойдут залипать в Тик Ток
Абсолютному большинству айтишников знать алгоритмы и вовсе не нужно, всё уже написано и оптимизировано под любые задачи. Бери и пользуйся. А эти задачки просто если скучно стало.
Хорошее видео. Жду следующего😉
Будет обязательно! ;) Благодарим, что смотрите!
Хорошая задача. Здорово, что предлагается решение несколькими способами!
мне надо было решить совсем другую задачу, но твоя помогла. Спасибо тебе, друх)
Класс! Очень рад)
Спасибо за видео!)
Благодарим за просмотр!
Спасибо за понятные объяснения и качественный контент
Приятно, что оказалось полезно!
Спасибо, интересная задача. Можете разобрать : Есть некоторое целое число, найдите максимальное число, которое вы можете получить удалив ровно одну цифру заданного числа?
И у вас тоже интересная задача. Можно её решить, например, так:
const getLargestByRemovingDigit = number => {
if (!Number.isSafeInteger(number)) {
throw `${number} is not a safe integer`;
}
const digits = String(number);
for (let i = 0; i < digits.length; i++){
if (digits[i + 1] > digits[i]) {
return Number(
digits.slice(0, i) + digits.slice(i + 1)
);
}
}
return +digits.slice(0, -1);
};
Спасибо!!
Как всегда познавательно.........
Рад, что понравилось) Спасибо за поддержку!
При большом объёме однородных данных скорее всего наиболее эффективным окажется подход, в котором все значения сперва отсортируют (и отбросят значения, которые заведомо больше суммы даже без суммирования), а потом двумя указателями начнут сходиться к середине и тестировать сумму.
Сложность по времени самого лучшего алгоритма сортировки O(n × log n). Это немного лучше, чем квадратичная сложность из первого варианта, но заметно хуже, чем линейная со второго.
Спасибо)еще было бы круто задачку на сдвиг массива влево-вправо на заданное число символов
Записали в список на будущее
Можно решить и за один проход:
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 [];
};
@front-end Science Скажите пожалуйста, нужна ли математика что бы работать в фронтенде? а то смотрю название всех видео и страшно становиться)
Достаточно холиварный вопрос :) Все дело в том, что есть очень много позиций в компаниях когда сложная математика совершенно не нужна. Когдавсе что требуется от фронтенд разработчика это сверстать (или собрать из готовых компонент) какой-то интерфейс и "подключить" к нему реальные данные из API. Но есть и случаи когда именно на фронтенде сосредоточена основная часть сложного client-side приложения. И вот тут начинаются случаи когда надо применять алгоритмы, оптимизировать вычисления с помощью математики, проектировать сложную архитектуру. Именно поэтому компании гиганты (типа Google, FB, Amazon, Яндекс, Netflix, Booking итд ) на собеседованиях спрашивают и алгоритмы и архитектуру помимо самого знания например js.
Спасибо! Очень познавательно!)
Можно и за один проход сделать, сложность правда так же самая по времени и по памяти
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 [];
}
Да, сложность будет такая же О(n), но фактически ваш вариант отработает в два раза быстрее. Ну а если мы знаем, что числа идут точно по порядку возрастания или убывания (отсортированные), то можно решить с помощью метода двух указателей и тогда затрат по памяти не будет.
Красивое решение, Лайк!
Благодарю! Рад что понравилось)
Я бы сначала отфильтровал массив и убрал оттуда все числа которые больше 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 [];
};
В плане читаемости отличный вариант. В плане сложности - не самый оптимальный вышел :)
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
Получилось 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%
Благодарю за варианты!
Еще один вариант решения за O(n^2) без вложенных циклов:
function sumOfTwo(arr, target) {
for (let i = 0; i < arr.length; i++) {
let required = target - arr[i];
if (arr.includes(required)) return [i, arr.indexOf(required)];
}
}
Привет) 👋 Частенько вас вижу в комментах под видео с задачами по JS. Спасибо, что делитесь своими вариантами решений. 🙂 Хочу уточнить, что означает первая строка тела функции 《if (nums.length === 2) return [0, 1];》 в первом/втором вариантах? 🤔
@@SerzhNesteruk если длина массива nums равна двум, вернуть массив [0,1]
@@EvilYou То есть, twoSum([3, 5], 9) должен будет вернуть [0, 1], а не пустой массив? 🤔
Мое решение :
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));
Можно и до одной строки сократить, но будет плохо читаться. Код вроде простой и должен работать корректно при любых числах (вроде) :)
Благодарю за решение. Тут есть один момент: функция должна возвращать индексы на которых стояли нужные нам числа. А это решение возвращает сами числа которые выдают нужную сумму.
@@frontendscience Спасибо, не заметил. Благодарю за крутую задачу и подробный разбор.
*тогда такой код:
const sumOfTwo = (arr, target) => {
let result = arr.filter(x => arr.includes(target - x));
let ind = [];
for (i of result) {
ind.push(arr.indexOf(i));
}
return result.length == 1 ? [] : ind;
};
console.log(sumOfTwo([2, 7, 11, 15], 9));
Хороший коментар.
Шо то меня сомненье гложет насчёт линейности. Ведь проверка есть ли элемент с таким ключом в объекте, по сути, не что иное как поиск в объекте ключа перебирая все элементы объекта. Да это быстрее чем цикл на JS, но всёравно это цикл в цикле и на больших числах будет заметно что нет никакой линейности.
ну, что тут скажешь. Разве, что изучите, как работают хэш таблицы, что такое О(1) - константная сложность и такие вопросы вам больше не придут в голову. Можете также почитать, что такое операция и Асимптотический анализ алгоритмов.
Сложность поиска значения по ключу, как в массиве, так и в хэш таблице (даже не смотря, что в JS и то и то объекты) будет константное О(1), проще говоря никакого перебора по сути и не будет, а если перебор и есть то он всегда константный из ограниченного количества вариантов (отправляю все также к хэш таблицам и коллизиям в них).
Думаю этого более чем достаточно, чтобы закрыть пробелы в знаниях.
Я бы еще на 11 строчку, на всякий случай, вместо проверки на flasy "numObject[diff]" сделал бы явкую проверку "numObject[diff] !== undefined". Если у нас в массиве с входными данными будет 0, то тут у нас может быть косяк.
P.S. я просто делал вариацию этой задачи, где возвращал не индксы, а сами числа.
Полезное дополнение! Благодарю
Второе - красивое решение
:)
А тут разве не надо было в ифе явно сравнивать значение с undefined? А то есть сомнения, если будет значение 0 в массиве) Спасибо за интересную задачку
Увидел, что уже было такое дополнение)
Супер
Второе решение заглохнет, если на вход придет массив типа [3, 3], а target будет 6
Почему вы так думаете?
@@ФуллБот потому что в объекте перезапишет 3, когда встретит его второй раз в цикле, и получится что-то вроде [1 , 1], вместо [0 , 1]
Я тоже подумал о дубликатах.Ведь каждый дубликат перезаписывает индекс.
При итерации через первый цикл запишется {3:1} . При итерации через второй цикл , когда i = 0 возвращается массив [0,1] , так как 0≠1 и число 3 находится в хэш таблице .
для двуух элементов можно решить дополнительным if в начале тела функции, что-то типа:
if (array.length === 2) {
return array[0] + array[1] === target ? [0, 1] : [];
}
2 элемента такой случай, когда цикл не нужен
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')
на питонсе потому что я искал другую задачу подсказки на кодварсе
а мне єта понрвилась и я решил
var twoSum = function(nums, target) {
const dict = new Map();
for(let i =0; i
Благодарю за решение - отличный вариант!
у меня один цикл получился
var twoSum = function(nums, target) {
let hash = {};
let arr = [];
for (let i = 0; i < nums.length; i++) {
let current = nums[i];
if(hash.hasOwnProperty(target - current)) {
arr.push(hash[target - current], i)
return arr;
}
hash[current] = i;
}
}
Нот бед как говорится
Для такого хеша лучше бы использовать Map, мне так кажется. Он оптимизирован под большие объёмы данных и добавление новых пар.
В вашей реализации размер хеша может исчисляться миллионами элементов.
Подскажите, пожалуйста, на чём основана реализация используемой здесь хэш-таблицы?
не совсем понял вопрос. В видео мы используем обычный объект. Можно использовать было бы и new Map. Для данной задачи это не принципиально.
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
Если можно вопрос к автору при больших массивах вот такой вариант не ускоряет работу? если такой вопрос уже был извиняюсь
const sumOfTwo = (arr, target) => {
const numObj = {};
const temp = []
for (let num of arr) {
if(num < target) temp.push(num);
}
for (let i = 0; i < temp.length; i++) {
numObj[arr[i]] = i;
}
for (let i = 0; i < temp.length; i++) {
const diff = target - arr[i];
if(numObj[diff] && numObj[diff] !== i) {
console.log([i, numObj[diff]]);
}
}
}
Нет - такой вариант не ускорит работу. Нам прийдется все равно вначале пройти весь массив. + мы еще и память дополнительную займем.
Но все равно благодарю за решение!
@@frontendscience но два вторых раза мы же уже проходим по отфильтрованным массивам... ну хорошо спасибо за ответ)
@@relaxnature6649 посмотрите это видео, возможно, вопросы отпадут: th-cam.com/video/Fu4BzQNN0Qs/w-d-xo.html
@@frontendscience посмотрел лайк поставил. все понял)
А если верных чисел будет больше двух, то получается цикл до них не доберется ? На первых двух правильных цифрах срабатывает return и цикл вместе с функцией обрывается. Или я что-то не понял.
Все верно. По условию задачи нет цели найти все возможные комбинации. Поэтому мы ищем первые попавшиеся и их возвращаем.
@@frontendscience, ок спс👍
const sumOfTwo = (arr, target) => {
const reducer = arr.reduce((acc, curr, index) => {
const difference = target - curr;
if (acc.hasOwnProperty(difference)) {
acc.answer = { indexOfValue1: acc[difference], indexOfValue2: index,
value1: difference, value2: curr};
}
acc[curr] = index;
return acc;
}, {});
return reducer.answer || "don't have solution";
}
если нужно, чтобы совпадений могла быть несколько, то просто делаем answer массивом и пушим в него найденные значения:
const sumOfTwo = (arr, target) => {
const reducer = arr.reduce((acc, curr, index) => {
const difference = target - curr;
if (acc.hasOwnProperty(difference)) {
acc.answer.push({
indexOfValue1: acc[difference], indexOfValue2: index,
value1: difference, value2: curr,
});
}
acc[curr] = index;
return acc;
}, { answer: [] });
return reducer.answer || 'dont have solution';
};
//изменения:
// arr.reduce( (...) => {
// if (...) {
// acc.answer.push( ... )
// }
//}, { answer: [ ] )
Пушка, спасибо за полезное решение) Внизу твоя идея без лишней суеты
P. S.
function sumOfTwo(array, target) {
let sum = 0
let result = []
for (let i = 0; i < array.length; i++) {
sum = target - array[i]
if (array.hasOwnProperty(sum)) {
result.push(i, array.indexOf(sum))
}
}
return result
}
console.log(sumOfTwo([2, 7, 11, 15], 9))
решение в один проход
const sumOfTwoBetter = (arr, target) => {
const arrMap = {};
const result = [];
for (let i = 0; i < arr.length; i++) {
const rest = target - arr[i];
if (arrMap[rest] === undefined) {
arrMap[arr[i]] = i;
} else {
result.push([arrMap[rest], i]);
}
}
return result;
};
console.log(sumOfTwoBetter([2, 7, 11, 15], 9));
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));
А как через битовую маску сделать?Хлопцы кто знает?
Да вроде так эту задачу не решить.
не какие решения у меня не вышло, я не знаю ничего
:(
Ну да, это замена второго цикла на потенциально огромную структуру с количеством элементов, пропорциональным размерности чисел в массиве.
Если у нас числа исчисляются десятками миллионов, то и хеш-таблица может потенциально содержать миллионы элементов.
Давай-ка на секундочку прикинем, сколько это по памяти?
Асимптотическая сложность для первого решения: O(1) по памяти и O(n²) по времени. Для втотого решения: O(n) по памяти и O(n) по времени.
Задействование дополнительной памяти для хранения миллионов элементов обычно не так критично (даже на современных мобильных устройствах), чем зависание скрипта на несколько суток 🙃
а исходный массив всегда отсортирован по возрастанию? хаха
По условию данной задачи - да! Хаха
for (let i = 0; i < nums.length; i++) {
const array1 = nums.slice(0, i+1);
const array2 = nums.slice(i+1);
const last = array1[array1.length - 1]
const second = array2.find((num) => num + last === target);
if (second !== undefined) {
const secondIndex = array2.findIndex((num) => num === second);
return [i, secondIndex + array1.length]
}
}
function sumOfTwo(array, sum) {
const numbers = Array
.from(new Set(array))
.filter(num => num < sum);
for(let i = 0; i < numbers.length; i++) {
let matchingNum = sum - numbers[i];
if(numbers.includes(matchingNum)) {
return [matchingNum, numbers[i]]
}
}
}
Nice solution!
Но это же не работает. Если значения в массиве были не уникальны, то индексы сместятся и результат будет некорректный
Какие О от эН? Что это такое? Зачем нам эта инфа и где этому учат ваще?
На днях выпустим видео про это. Нажимайте на колокольчик, чтоб не пропустить:)
Був би цікавий алгоритм пошуку всіх чисел з масиву, які в сумі дають число N.
А так, дякую за відео!
решение только для массивов со всеми уникальными элементами
Да!!! Потому что именно такое условие!
@@АртурДемидов-г7ф А "люди" пробовали читать описание задачи в видео? Я уже не говорю о том чтобы зайти на leetcode.
PS: Люди - это один человек оставивший комментарий
Сумма трёх
function sumtwo(arr, target) {
let s = 0;
let result = [];
for (let i = 0; i < arr.length - 2; i++) {
if (arr[i]
сложность алгоритма не смущает?)))
@@ДмитрийНормов-ю6ц Не-а.
@@vozay вложенные циклы.
@@ДмитрийНормов-ю6ц А как найти все тройки или пары? Единственное, как можно упростить: во втором цикле найти дополнение до суммы и искать в третьем цикле подходящее число из оставшихся, как у автора ролика.
И, если цифры могут быть отрицательные, убрать проверку на превышение целевой суммы.
kaef
Изи
Да, так тоже ок.
спасибо за решения!
В условии задачи, нужно вернуть массив индексов первой суммы или всех возможных сумм?
у вас результаты 2-х решений дадут разный вариант на этом кейсе: sumOfTwo([-2,11,15,2,7], 9)
Мой вариант почти такой же как у вас 1-й не-потимальный)
const sumOfTwoMy = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
for (let j = i+1; j < arr.length; j++) {
if (arr[i]+arr[j] === target) {
return [i, j]
}
}
}
return [];
}
const sumOfTwo = (arr, num) => {
const a = [];
arr.forEach((e,i) => {
const clone = [...arr];
clone[i] = null;
if (clone.includes(num - e)) a.push(i)
});
return a;
}
console.log(sumOfTwo([4, 5, 4, 15], 8));
Классно, а что будет, если поискать сумму 3 в массиве из [1, 2, 3, 4, 5, 0, 0, 0, ...., 0, 0] в котором 10000000 элементов?