LeetCode – 3Sum (с JavaScript)

Сегодня я собираюсь показать, как решить проблему алгоритма 3 суммы.

Вот проблема:

В моем предыдущем блоге я говорил о решении алгоритма 2SUM. Для этой проблемы. Мы могли бы использовать хэш -таблицу для хранения каждого числа, аналогичного решению в алгоритме 2SUM. Тогда мы могли бы сделать двойной »для« петлей »и проверить, существует ли дополнительный номер текущего номера в таблице. Но это не был бы наиболее эффективным способом решения этой проблемы.

Вместо этого я собираюсь решить эту проблему, используя два указателя, которые дадут нам O (n^2) сложность времени. При таком подходе первое, что нам нужно сделать, это сортировать заданный массив в порядке возрастания.

После сортировки массива мы собираемся итерации через него и установили два наших указателя. Левый указатель будет установлен на число, которое появляется сразу после текущего номера, и правый указатель будет установлен на номер в конце массива. Затем мы найдем нашу текущую сумму, которая является суммой нашего текущего номера, левого номера и правого номера.

Теперь мы проверяем, равна ли наша текущая сумма нашей целевой сумме, которая в этом случае равна 0.

Если это равно, мы просто добавляем эти три числа в наш окончательный массив (триплеты).

Если текущая сумма меньше 0, мы перемещаем левый указатель вправо на один, чтобы увеличить сумму. Поскольку мы ранее отсортировали заданный массив в восходящем порядке, мы знаем, что каждое число больше, чем число слева.

Если текущая сумма превышает 0, потому что мы знаем, что каждое число меньше числа справа, мы можем переместить правый указатель влево на один, чтобы уменьшить сумму.

var threeSum = function(array) {
     array.sort((a,b) => a - b);
    const triplets = [];

    for(let i=0; i < array.length - 2; i++){
        if(array[i] != array[i-1]){ // making sure our solution set does not contain duplicate triplets
            let left = i + 1;
          let right = array.length - 1;

            while (left < right){
                const currentSum = array[i] + array[left] + array[right];
                if (currentSum === 0){
                    triplets.push([array[i], array[left], array[right]]);
                    while(array[left] == array[left + 1]) left ++
                    while(array[right] == array[right - 1]) right -- // making sure our solution set does not contain duplicate triplets
                    left ++;
                    right --;
                } else if(currentSum < 0) {
                    left ++
                } else if(currentSum > 0){
                    right --
                }
            }
        }
    }
    return triplets
};

Оригинал: “https://dev.to/urfan/leetcode-3sum-with-javascript-4b8j”