Пожалуйста, прочитайте описание проблемы здесь: https://leetcode.com/problems/two-sum/
Из описания задачи видно, что нам дана функция с двумя переменными:
- Массив со списком чисел
- Целое число, являющееся целевым значением суммы.
Мы должны вернуть два индекса двух чисел, которые при сложении вместе мы получим целевое значение.
В этой статье я покажу вам два способа решения проблемы с помощью Javascript. Первое решение будет наивным, а следующее решение будет оптимизированным.
Решение 1 (Наивный подход)
Для первого решения мы будем использовать два вложенных цикла.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
/*
*1. The Outer loop, picks one value from the array at a time.
*/
for(let i=0;i<nums.length;i++){
/*
*The inner loops through the array(separately) and compares
*each value with with the value picked by the outer loop.
*/
for(let j=0;j< nums.length;j++){
/*
*To prevent numbers from the same index from being
*compared we check ensure indices i and j are not equal.
*/
if(j!=i){
/*If the difference between the target and the loop1
*value are equal to the inner loop value we have
*found a match and we return
*the two indices
*/
if((target-nums[i])==nums[j]){
return [i,j]
}
}
}
}
};
Решение работает, хотя его временная сложность равна O(n^2), что означает, что количество запусков кода равно квадрату длины массива nums. Например, если у нас есть nums=[2,7,9,11] и target=9, это будет лучший сценарий нашего кода, поскольку цель будет найдена, когда мы итерируем внешний цикл один раз и внутренний цикл дважды, т.е. значение будет [0,1], так как 2+7=9. Другой сценарий — когда у нас есть решения в конце массива nums, т. е. nums=[8,11,2,7] и target=9. В этом случае внешний цикл будет выполняться 3 раза, прежде чем будет найдена одна часть решения, то есть 2. Каждый раз, когда внешний цикл выполняется один раз, внутренний цикл выполняется четыре раза, что означает, что в этом случае наши внутренние циклы выполняются 12 раз, прежде чем найти решение. В еще худшем случае, когда у нас нет решения, например, nums=[8,11,3,3] и target=9, это означает, что наш внешний цикл будет выполняться четыре раза. Внутренний цикл будет выполняться четыре раза для каждой итерации внешнего цикла. Следовательно, общее количество запусков внутреннего цикла будет 4*4=16. Если длина массива nums равна 4, внутренний цикл выполняется не более 16 раз, если длина массива nums равна 10 000, внутренний цикл выполняется не более 10 000 * 10 000 = 100 000 000 раз. Поэтому максимальное количество запусков внутреннего цикла равно квадрату длины массива nums, следовательно, обозначение сложности O(n^2). Поскольку мы не храним никаких данных, сложность нашего хранилища составляет O (1), т. е. она не увеличивается с размером входных данных.
Решение 2
Для этого решения мы хотим улучшить нашу сложность времени выполнения с O (n ^ 2) до O (n), однако мы будем использовать карты. Карты можно использовать для хранения пар ключ-значение. Поэтому для каждого сохраненного ключа у нас должно быть значение, обеспечивающее более быстрый способ получения информации. В нашем случае ключом является разница между целью и числом по текущему индексу. Значением карты является текущий индекс.
Наше оптимизированное решение будет иметь сложность хранения O(n).
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
//We initialize our map using JS inbuilt class
let map=new Map();
/*
*We only use one loop to iterate through the array once,
*therefore improving on the time complexity of our solution.
*/
for(let i=0; i<nums.length; i++){
//We check if the current number exists as a key in our map.
if(!map.has( nums[i] )){
/*If the number does not exist, we calculate the
*difference between the target and the current number,
*set is as a key with the current index as a value.
*/
map.set( target-nums[i] , i )
} else {
/*If the current number exists, it means there is
*another number in our map which if added with the
*current number we get the target. We use the map.get()
*function to retrieve the index. We then return the two
*indexes.
*/
return [ map.get( nums[i] ) , i ]
}
}
};
