Моля, прочетете описанието на проблема тук: 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 ]
}
}
};
