Сегодня мы решаем задачу о четырех суммах 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, когда мы используем метод двух указателей для поиска пар, которые в сумме дают целевое значение. Этот подход может быть более эффективным, чем решения грубой силы и хеш-таблицы, поскольку он устраняет элементы, которые нам не нужно проверять, используя метод двух указателей и сначала сортируя массив. Однако для хранения стека рекурсии требуется дополнительное пространство, и он должен хорошо обрабатывать базовый случай, чтобы предотвратить бесконечную рекурсию.
В заключение, есть несколько способов решить проблему четырех сумм, каждый из которых имеет свой собственный набор компромиссов. Метод грубой силы прост в реализации, но имеет высокую временную сложность, решение с использованием хеш-таблицы более эффективно, но занимает дополнительное пространство, метод двух указателей эффективен и не занимает дополнительного места, а стратегия «разделяй и властвуй» также эффективен, но основан на рекурсии и также должен обрабатывать базовый случай. Наилучшее решение зависит от ограничений и требований конкретной проблемы.