[Условие] Leetcode #1. Two sum

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

У нас есть массив чисел nums и число target.
Нужно написать функцию, которая возвращает индексы двух чисел из массива nums, которые в сумме дают target. Нельзя использовать один и тот же элемент дважды.
Считаем, что у задачи всегда есть решение и оно только одно.

Отдельный пункт: постараться найти решение, у которого временная сложность меньше O(n^2).

Кейс #1: 
nums = [2,7,11,15]
target = 9
output = [0,1]

Кейс #2:
nums = [3,2,4]
target = 6
output: [1,2]

Кейс #3:
nums = [3,3]
target = 6
output = [0,1]

#easy #arrays #twopointers #hashtable

@leetcode_furrycat

[Решение] Leetcode #1. Two sum

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

👉 Решение #1. Самое очевидное

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

Временная сложность - O(n^2), так как мы дважды перебираем массив.

👉 Решение #2. Хеш-таблица

Заводим хеш-таблицу hash.
Перебираем каждый элемент массива nums в цикле.
Вычитаем его из target - это искомая пара.
Смотрим, есть ли эта пара в hash. Если есть - решение найдено.
Если нет, записываем текущий элемент в хеш. Ключом является сам элемент, чтобы его было просто найти, а значением - его индекс в массиве.

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

👉 Решение #3. Два указателя

Сортируем массив, так чтобы числа в нем шли по порядку, например, от меньше к большему.
Устанавливаем один указать в начало массива (с меньшего числа) , а второй - в конец (с большего числа).
Складываем элементы под указателями. Если полученная сумма больше target, двигаем правый указатель влево (уменьшаем число под ним).
Если полученная сумма меньше target, двигаем левый указатель вправо (увеличиваем число под ним).

Временная сложноть - O(n * log n). Это сложность алгоритма сортировки. Сам поиск пары имеет сложность O(n).

Видео с разбором всех трех решений (англ.)

#easy #arrays #twopointers #hashtable

@leetcode_furrycat

Решенные задачи

1 - Two sum
2 - Add two numbers
3 - Longest Substring Without Repeating Characters
4 - Median of Two Sorted Arrays
5 - Longest Palindromic Substring
10 - Regular Expression Matching
11 - Container With Most Water
15 - 3Sum
33 - Search in Rotated Sorted Array
53 - Maximum Subarray
121 - Best Time to Buy and Sell Stock
152 - Maximum Product Subarray
153 - Find Minimum in Rotated Sorted Array
217 - Contains Duplicate
238 - Product of Array Except Self

По сложности

#easy
#medium
#hard

По темам и методам решения

#strings
#arrays
#linkedlists
#dp
#divideandconquer
#twopointers
#hashtable
#prefixsum

#ретро

[Условие] Leetcode #121. Best Time to Buy and Sell Stock

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

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

Кейс 1:
prices: [7, 1, 5, 3, 6, 4]
ответ: 5
объяснение: выгоднее всего купить акцию во второй день (цена = 1) и продать в пятый (цена = 6)

Кейс 2:
prices: [7,6,5,4,3,1]
ответ: 0
объяснение: с этой акции в этот период нельзя получить прибыль

Ограничения:

prices.length = [1, 10^5]
prices[i] = [0, 10^4]

#easy #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #121. Best Time to Buy and Sell Stock

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

Используем подход с двумя указателями (`left` и `right`). Изначально устанавливаем их на первый и второй день.

Если цена между этими днями упала, то этот период нам не нужен. Можем сдвинуть указатели - left встает на место right, а right сразу же за ним.

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

Повторяем эту операцию в цикле, пока right не достигнет конца массива.

Таким образом мы учитываем все периоды, в которые была прибыль.
Если обнаруживаем падение цены (`right` меньше `left`), то начинаем отсчет с этого места, так как для всех дальнейших периодов прибыль с нового `left` будет больше, чем со старого.

#easy #arrays #twopointers

@leetcode_furrycat

[Условие]. 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