Leetcode: интуитивный подход с двумя суммами

Представьте себя счастливым владельцем сувенирного магазина в отеле Spot-On Change. При закрытии кассы вы замечаете превышение 8 евро. Похоже, гость не получил точную сдачу. Это может запятнать репутацию отеля. Чтобы избежать этого, вы решаете разгадать тайну неправильного изменения. Открыв кассу магазина, вы обнаруживаете, что ошибка произошла на двух разных счетах!

Вы придумываете план: посетить каждую комнату и спрашивать у гостей, какую сдачу они получили в магазине, пока не обнаружите обе комнаты с неправильными купюрами. Придя на первый этаж, гость сообщает, что получил сдачу в размере 4 евро. Вы подсчитываете, что вам нужно найти число, которое при добавлении к 4 евро дает 8. При переезде на второй этаж сдача гостя составляет 5 евро. 4 + 5 дает 9, значит, это не может быть этот… Пятый этаж, шестой… Десятый, НЕТ, НЕТ, НЕТ!

Поскольку с первой попытки вы не нашли значение, вы спускаетесь на второй этаж и начинаете заново расспрашивать всех гостей об их сдаче, чтобы можно было сравнить ее со значением со следующего стартового этажа, утомительно, не так ли? это? В информатике этот метод поиска называется «грубой силой» — чрезвычайно медленный метод поиска, который работает путем сравнения одного элемента со следующими в массиве.

Это отнимает много времени и неэффективно: представьте, что вы несколько раз поднимаетесь и спускаетесь по всем этажам отеля Spot-On Change Hotel! Это непрактично ни для вас, ни для компьютера.

Если вам интересно, как это перемещение вверх и вниз по этажам будет происходить в программе, на JavaScript это будет выглядеть так:

 twoSum(nums, target) { 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]; } } } }

Спокойно оценив ситуацию, вы понимаете, что есть более эффективный способ найти двух гостей с неправильной сдачей.

Вы уточняете свою первоначальную математическую интуицию о том, что 9 евро равны x + y. Применив немного арифметики, вы понимаете, что: x + y = 9 — это то же самое, что сказать, что y = 9 — x, и это имеет решающее значение для повышения эффективности вашего поиска.

Еще одна вещь, которая изменилась в вашей стратегии: теперь вы будете брать в блокнот значения, которые вам говорят гости, так что вам не придется запрашивать одно и то же значение дважды для гостей, и вам не придется тратить день подъемов и спусков по лестнице. (Какое ужасное время для поломки лифта!).

С новыми инструментами в руках вы направляетесь на второй этаж, где гость сообщает вам, что у него есть сдача на 5 евро. Вы записываете это как {5: 0}, что указывает на значение 5 в позиции 0. Заменяя x на 5 в уравнении, вы вычисляете y = 8–5, в результате чего y = 3. Поскольку ваш блокнот все еще пуст, вы не у вас нет записанного числа 3, которое было бы дополнительным числом к 5, чтобы получить результат 8. Затем вы записываете число 5 в свой блокнот (не забывайте всегда записывать число, проверенное на данный момент, а не его дополнение; вы будет использовать дополнение только для сравнения его с записанным вами целевым числом). Вы переходите ко второму гостю, который упоминает, что получил сдачу в размере 2 евро. Применяя формулу еще раз: y = 8–2 => y = 6, вы проверяете свою запись и не находите ни одной цифры 6. Таким образом, вы добавляете 2 к своей записи, которая теперь имеет вид {5: 0, 2:1}. Продолжая поиски, следующий гость сообщает, что получил 3 евро сдачи. Вычисляешь еще раз: y = 8–3 => y = 5. Бинго! У вас в блокноте записана цифра 5! Гость с 0 этажа дополняет гостя со 2 этажа! Этот подход известен как хеш-таблица, и он намного быстрее и эффективнее как для вас, так и для компьютера. В JavaScript это будет реализовано следующим образом:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Это простая задача из Leetcode , которая становится простой только после того, как вы поймете лежащие в ее основе концепции. Я рекомендую вам попытаться решить проблему самостоятельно и потратить некоторое время на то, чтобы построить за ней интуицию, создать собственную аналогию, просмотреть и попробовать написать псевдокод, прежде чем переходить к решению.

Надеюсь, моя аналогия помогла вам лучше понять концепцию задачи «две суммы».

Увидимся в следующий раз!