Даден е масив от цели числа nums и цяло число target, върнете индексите на двете числа, така че сборът им да дава target.

Може да приемете, че всеки вход ще има точно едно решение и не можете да използвате същия елемент два пъти.

Можете да върнете отговора в произволен ред.

Пример

Вход: [2,7,11,15]

цел=9

Изход: [0,1]

Бележки

Винаги ще има решение и не можем да използваме един и същ елемент два пъти (Напр.: 11 не може да се появи в масива два пъти)

Как да използвате Карти

Картата съдържа двойка ключ-стойност и запомня оригиналния ред на ключовете.

let myMap = new Map();
myMap.set('Hello',2); //set a key value pair
myMap.has('Hello'); //returns true or false if myMap has key 'Hello'
myMap.get('Hello'); //return the value of 'hello' which is 2
myMap.delete('Hello'); //deletes key 'Hello' from the myMap

Подход

  1. Създайте карта
  2. Итерация през масива nums
  3. Създайте променлива, която ще проверява дали съществува число, което сме съхранили в картата. Ако номерът, който търсим, е в картата, той няма да върне недефинирано. В противен случай променливата ще остане недефинирана.
  4. Ако номерът вече е в картата, върнете стойността на ключа, който намерихме, и текущия индекс на цикъла.
  5. Ако не е в картата, създайте променлива за съхраняване на числото, което търсим минус текущия елемент. Също така, запазете двойката ключ стойност в картата, която създадохме.

Код

var twoSum = function(nums, target) {
    let myMap = new Map();
    for(let i=0;i<nums.length;i++){
        let currentVal = myMap.get(nums[i]);
        if(currentVal >= 0){
            return [currentVal,i];
        }else{
            let numToFind = target — nums[i];
            myMap.set(numToFind,i);
        }
     }
};

Времева сложност

O(n): Преминаваме през масива само веднъж, следователно е o(n).

Космическа сложност

O(n): Създаваме карта и съхраняваме стойности в нея от масива, следователно това е o(n).