[Условие] 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 #2. Add two numbers

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

Есть два связных списка, каждый из которых представляет неотрицательное число. Цифры (разряды) при этом идут в обратном порядке.
Узел связного списка представлен классом ListNode с полями val и next.

Пример: число 307 будет выглядеть как [7, 0, 3] - соответственно каждое число - это объект ListNode.

Задача: нужно сложить два этих неотрицательных числа, представленных в виде списков, и вернуть результат тоже в виде связного списка.

Пример 1:
l1 = [2,4,3]
l2 = [5,6,4]
Output: [7,0,8] 
Объяснение: 342 + 465 = 807

Пример 2: 
l1 = [0]
l2 = [0]
Output: [0]

Пример 3:
l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]
output = [8,9,9,9,0,0,0,1]

Ограничения:
- ведущих нулей у чисел нет, но число вполне может быть равно нулю
- в каждом списке от 1 до 100 узлов
- каждый узел имеет значение от 0 до 9

#medium #linkedlists

@leetcode_furrycat