[Условие]. Leetcode 15. 3Sum

Ссылка на задачу на Leetcode
Решение

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

Кейс 1
nums = [-1,0,1,2,-1,4]
ответ: [ [-1, -1, 2], [-1, 0, 1] ]

Кейс 2
nums = [0,1,1]
ответ: []

Кейс 3
nums = [0,0,0]
ответ: [[0,0,0]]

#medium #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #15. 3Sum

Условие задачи

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

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

function threeSum(nums: number[]): number[][] {
    if (nums.length < 3) return [];

    nums.sort((a, b) => a - b);
    if (nums[0] > 0) return [];

    const triplets = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break;
        if (nums[i] === nums[i - 1]) continue;

        let j = i + 1;
        let k = nums.length - 1;
        
        while(j < k) {
            const sum = nums[i] + nums[j] + nums[k];
            if (sum === 0) {
                triplets.push([nums[i], nums[j], nums[k]]);
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }

    return triplets;
}

#medium #arrays #twopointers

@leetcode_furrycat

[Условие]. Leetcode 11. Container With Most Water

Ссылка на задачу на Leetcode
Решение

У нас есть несколько вертикальных линий, расположенных последовательно через равное расстояние. На вход получаем массив, в котором содержатся их высоты.
Задача - найти максимальную площадь прямоугольника, сторонами которого являются две из этих линий.

Кейс 1
height = [1,8,6,2,5,4,8,3,7] (на картинке)
Ответ: 49 (между линиями с высотой 8 и 7)

#medium #arrays #twopointers

@leetcode_furrycat

[Решение]. Leetcode 11. Container With Most Water

Условие задачи

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

function getVolume(height: number[], left: number, right: number): number {
    const h1 = height[left]
    const h2 = height[right]
    return Math.min(h1, h2) * (right - left)
}

function maxArea(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let max = 0

    while(left < right) {
        max = Math.max(max, getVolume(height, left, right))

        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }

    return max
}

#medium #arrays #twopointers

@leetcode_furrycat

Blind 75. Arrays

Небольшое ретро по задачкам из раздела Массивы:

1 - Two sum (easy)
11 - Container With Most Water (medium)
15 - 3Sum (medium)
33 - Search in Rotated Sorted Array (medium)
53 - Maximum Subarray (medium)
121 - Best Time to Buy and Sell Stock (easy)
152 - Maximum Product Subarray (medium)
153 - Find Minimum in Rotated Sorted Array (medium)
217 - Contains Duplicate (ease)
238 - Product of Array Except Self (medium)

Какие подходы к решению использовались:

👉 Два указателя (#twopointers)

Используется, когда "второй" элемент всегда идет после "текущего". Часто используется для отбора последовательно идущих элементов, которые в комбинации соответствуют определенному условию.

- два/три элемента, составляющие определенную сумму (Two sum, 3Sum)
- две линии, составляющие прямоугольник наибольшей площади (Container With Most Water)
- две даты, между которыми акция росла больше всего (Best Time to Buy and Sell Stock)

👉 Хеш-таблица (#hashtable)

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

- Быстро найти второе слагаемое для известной суммы и первого слагаемого (Two sum)
- Найти дубликаты ( Contains Duplicate)

👉 Разделяй и властвуй (#divideandconquer)

Используется с отсортированными массивами, когда есть возможность определить, в какой части массива находится нужное значение. Часто используется для поиска (бинарный поиск) элемента (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array). Но может использоваться и в более сложном виде, например, для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Рекурсия (#recursion)

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

Например, мы использовали рекурсию для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Динамическое программирование (#dp)

У динамического программирования есть несколько разновидностей: мемоизация и табуляция. Сюда же можно включить вычисление префиксных сумм (#prefixsum). Подвидом ДП является алгоритм Кадане.
Суть метода в том, что мы используем результаты предыдущих вычислений.
Динамическое программирование часто используется в задачах с массивами для нахождения подмассива с заданными свойствами, например, с максимальной суммой (Maximum Subarray, Maximum Product Subarray)
Также с его помощью (префиксные суммы) мы вычисляли произведение всех элементов массива кроме текущего (Product of Array Except Self).

👉 Set

При работе с массивами может быть полезна структура данных Set, которая позволяет быстро удалить дубликаты из массива (Contains Duplicate), а также обеспечивает быстрый доступ к элементам массива по их значению.

#arrays #ретро

@leetcode_furrycat