Итак, вы делаете первый шаг к решению алгоритмов на LeetCode, а? Отличная работа! Вы только что закончили его, однако вы можете получить сообщение о том, что вы решаете его быстрее, чем 25% отправленных материалов. Так что же происходит?
Скорее всего, вы решили ее с помощью метода грубой силы, что неплохо, вы смогли решить проблему, однако возможность эффективного написания кода чрезвычайно важна.
Вот решение, которое я придумал, без необходимости писать цикл внутри цикла
var twoSum = function(nums, target){
if(nums.length === 2) return [0, 1];
let hashMap = {};
for(let i = 0; i < nums.length; i++) {
let find = target - nums[i];
let found = hashMap[find]
if(found !== undefined) {
return [found, i]
} else {
hashMap[nums[i]] = i;
}
}
};
if(nums.length === 2) return [0, 1];
Что происходит здесь с первым оператором if, так это то, что если длина массива равна 2, вы просто возвращаете [0, 1], потому что это будет единственное число, которое можно добавить к цели.
let hashMap = {};
Затем мы создали хеш, в котором будем хранить числа, которые мы перебираем.
for(let i = 0; i < nums.length; i++) {
}
Теперь мы хотим перебрать данный массив, написав цикл for
let find = target - nums[i]; let found = hashMap[find]
Внутри цикла for мы хотим написать переменную с именем «find», в которой будет храниться число, которое мы хотим искать внутри массива.
Для этого мы берем наше целевое число и вычитаем его на число на текущей итерации. Например, если ваша цель - 9, а ваше текущее число - 3, вы вычитаете 3 из 9, что дает вам 6, которое затем будет числом, которое вы ищете.
Как только мы найдем номер, мы увидим, существует ли он в хэш-карте, которую мы создали ранее.
if(found !== undefined) {
return [found, i]
} else {
hashMap[nums[i]]
}
Теперь вот последний шаг
Во время каждой итерации мы будем видеть, существует ли нужный нам ключ в нашей hashMap. Если это так, мы возвращаем [found, i], потому что это будут 2 числа, которые в сумме будут соответствовать нашей цели.
Если ключ не существует, мы просто создаем его, и в конечном итоге с помощью нашего цикла мы сможем найти ключ, который сможет суммировать с нашей текущей итерацией до нашей цели.
Я надеюсь, что это чтение помогло решить twoSum без использования метода грубой силы. Решать алгоритмы всегда сложно, когда вы только начинаете, особенно когда правильного ответа может быть недостаточно. Однако со все большей практикой это становится легче, потому что вы сможете распознать аналогичные закономерности и проблемы, с которыми сталкивались раньше. Удачи, программисты!
