Алгоритм двух сумм - использование индекса поиска - Javascript алгоритм

Question

Вопрос

Учитывая массив целых чисел, вернуть индексы двух чисел так, чтобы они складывались до заданной c цели.

Вы можете предположить, что у каждого входа будет только одно решение, и вы не можете использовать один и тот же элемент дважды.

Но я специально хочу использовать findIndex () для решения этой проблемы. Проблема в том, что нам нужно сложить два индекса! Не только один.

function twoSum(arr, target){

let relevantArr = [];

let newArr = arr.slice(0,);

function test(){

return newArr.findIndex(added);

}

function added (a, b) {
  a + b == target;

}


return relevantArr
}



console.log(twoSum([2, 7, 11, 15], 9))

Помощь оценена, если вы знаете способ сделать эту работу!

Answer 1

Действительно, если вы хотите, чтобы использовал findIndex, тогда его возвращаемого значения никогда не будет достаточно, поскольку это только один индекс. Вы можете использовать «побочный эффект» и использовать другую переменную для хранения второго индекса. Чтобы найти второй индекс, не используйте снова findIndex, так как это излишне. Используйте indexOf и убедитесь, что он сканирует только часть массива, которая идет после первого индекса (с использованием второго аргумента indexOf):

function twoSum(arr, target) {
    let j = -1; // Needs to be accessible by the following function:

    function added(val, i) {
        // modify the variable outside of this function scope:
        j = arr.indexOf(target - val, i + 1);
        return j >= 0; // true if success
    }

    // findIndex will modify j, which we add to the pair
    return [arr.findIndex(added), j]; // will be [-1, -1] when not found
}
console.log(twoSum([2, 7, 11, 15], 9)); // found
console.log(twoSum([2, 7, 11, 15], 100)); // not found

Функция added теперь является «грязной» функцией, поскольку она изменяет переменную во внешней области видимости. Но это ближе всего к тому, что вы пытались сделать.

Требуется больше for l oop (вместе с indexOf). А для больших массивов вам будет полезно сначала создать карту, поэтому вам не нужен линейный поиск в пределах этого l oop, а только постоянный.

Answer 2

Вы можете l oop на элементах массива и попытаться найти его дополнение, чтобы получить цель. Если дополнение не найдено, findIndex возвращает -1, и вы проверяете следующее.

function twoSum(arr, target){
    for(let i = 0, len = arr.length ; i < len ; ++i)
    {
        // try to find an item so that its sum with arr[i] is equal to the target
        let j = arr.findIndex(item => item + arr[i] == target); 
        if(j != -1)
        {
            // we found the element, we can return the answer
            return [i, j];
        }
    }
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0,1]
console.log(twoSum([2, 7, 11, 15], 18)); // [1,2]