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

Данный массив nums из n целых чисел и целочисленная цель, существуют ли элементы a, b, c и d в nums такие, что a + b + c + d = target? Найдите все уникальные четверки в массиве, который дает целевую сумму.

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

Есть несколько способов решить эту проблему, но в этой статье мы рассмотрим четыре разных решения:

Решение грубой силы
Использование хэш-таблицы
Техника двух указателей
Стратегия «разделяй и властвуй»

1. Решение методом грубой силы
Решение методом грубой силы является наиболее простым подходом к решению этой проблемы. Мы можем просто перебрать массив и сравнить каждую возможную четверку элементов, чтобы увидеть, соответствуют ли они целевому значению.

function fourSum(nums, target) {
    let result = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                for (let l = k + 1; l < nums.length; l++) {
                    if (nums[i] + nums[j] + nums[k] + nums[l] === target) {
                        result.push([nums[i], nums[j], nums[k], nums[l]]);
                    }
                }
            }
        }
    }
    return result;
}

Это решение имеет временную сложность O(n⁴), что неэффективно для больших массивов, поскольку для массива размера n нам нужно проверить nnn*n четверок элементов.

2. Использование хэш-таблицы
Другой подход заключается в использовании хэш-таблицы для хранения элементов при переборе массива. Для каждого элемента мы проверяем, есть ли уже триплет (целевой минус текущий элемент) в хеш-таблице. Если это так, мы нашли три элемента, которые в сумме составляют целевое значение.

function fourSum(nums, target) {
    let result = [];
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                const complement = target - (nums[i] + nums[j] + nums[k]);
                if (complement in hash) {
                    result.push([nums[i], nums[j], nums[k], complement]);
                } else {
                    hash[nums[k]] = true;
                }
            }
        }
    }
    return result;
}

Это решение имеет временную сложность O(n³), что более эффективно, чем решение методом грубой силы. Мы перебираем массив один раз и для каждого элемента проверяем все остальные возможные триплеты с временной сложностью O(n²) и проверяем, находится ли его дополнение в хеш-таблице, что является операцией с постоянным временем.

3. Метод двух указателей
Другой подход заключается в использовании метода двух указателей, который имеет временную сложность O(n²). Общая идея состоит в том, чтобы сначала отсортировать массив, а затем выполнить итерацию по массиву, используя два указателя, один из которых начинается слева, а другой — справа. Для каждого элемента мы используем два указателя, чтобы найти пару элементов, сумма которых равна целевому значению минус текущий элемент.

function fourSum(nums, target) {
    let result = [];
    // check if the array length is less than 4 
    if(nums.length < 4) return result;
    // sort the array in ascending order
    nums.sort((a, b) => a - b);
    // outer loop from 0 to the second last element
    for (let i = 0; i < nums.length - 3; i++) {
        // Skip the element if it's the same as the previous one to avoid duplicates
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        // inner loop from i+1 to the third last element
        for (let j = i + 1; j < nums.length - 2; j++) {
            // Skip the element if it's the same as the previous one to avoid duplicates
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            // initialize left pointer
            let left = j + 1;
            // initialize right pointer
            let right = nums.length - 1;
            while (left < right) {
                // calculate the sum of 4 elements
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    // if sum equals target add the elements to the result
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    // Skip the duplicate elements
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

Это решение имеет временную сложность O(n²), что более эффективно, чем решения с использованием грубой силы и хеш-таблиц. Техника двух указателей основана на сортировке массива, а затем итерации по массиву с использованием двух указателей, которые начинаются слева и справа, и мы перемещаем их друг к другу на основе суммы элементов, тем самым удаляя элементы, которые нам не нужны. Проверять.

4. Стратегия «разделяй и властвуй»
Еще один способ решить проблему 4Sum — использовать стратегию «разделяй и властвуй», когда вы делите проблему на более мелкие подзадачи и рекурсивно решаете их. Этот подход также может иметь временную сложность O(n²) в зависимости от реализации и конкретного варианта использования.
Примером использования стратегии «разделяй и властвуй» является использование задачи «K-Sum» в качестве подзадачи, где k = 2, чтобы решить задачу 4-Sum. Мы используем технику двух указателей для решения задачи k-sum и рекурсивно вызываем ее для k = 2, пока не достигнем k = 4.

function fourSum(nums, target) {
    let result = [];
    // check if the array length is less than 4 
    if(nums.length < 4) return result;
    // sort the array in ascending order
    nums.sort((a, b) => a - b);
    function kSum(nums, target, k, start, current, result) {
        if(start === nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
            return;
        if(k === 2) {
            let left = start;
            let right = nums.length - 1;
            while (left < right) {
                const sum = nums[left] + nums[right];
                if (sum === target) {
                    result.push(current.concat([nums[left], nums[right]]));
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        else {
            for (let i = start; i < nums.length - k + 1; i++) {
                // Skip the duplicate elements
                if (i > start && nums[i] === nums[i - 1]) continue;
                kSum(nums, target - nums[i], k - 1, i + 1, current.concat([nums[i]]), result);
            }
        }
    }
    kSum(nums, target, 4, 0, [], result);
    return result;
}

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

Функция kSum принимает 6 параметров:

nums: входной массив целых чисел.
target: целевое значение, которое мы пытаемся найти в сумме.
k: текущее значение k, начиная с 4 и уменьшаясь на 1 при каждом рекурсивном вызове.
start:начальный индекс текущего подмассива, который мы рассматриваем.
current: текущая четверка, которую мы строим.
результат: окончательный массив четверок, которые в сумме составляют целевое значение.

Функция начинает с проверки правильности текущего подмассива (т. е. начальный индекс меньше длины массива, а первый и последний элементы подмассива, умноженные на k, меньше или больше целевого значения соответственно). Если подмассив недействителен, функция возвращает значение.

Если k равно 2, мы используем метод двух указателей, чтобы найти пары в подмассиве, которые в сумме составляют целевое значение минус текущий четверной.

В противном случае мы перебираем подмассив и рекурсивно вызываем функцию kSum с k, уменьшенным на 1, и текущей четверкой, к которой добавляется текущий элемент. Таким образом, мы разбиваем проблему на более мелкие подзадачи и используем метод двух указателей в качестве базового случая, когда k = 2.

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

Стратегия «разделяй и властвуй» позволяет нам уменьшить размер проблемы, разбивая ее на более мелкие подзадачи и рекурсивно решая их. Базовым случаем этой рекурсии является случай, когда k = 2, когда мы используем метод двух указателей для поиска пар, которые в сумме дают целевое значение. Этот подход может быть более эффективным, чем решения грубой силы и хеш-таблицы, поскольку он устраняет элементы, которые нам не нужно проверять, используя метод двух указателей и сначала сортируя массив. Однако для хранения стека рекурсии требуется дополнительное пространство, и он должен хорошо обрабатывать базовый случай, чтобы предотвратить бесконечную рекурсию.

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