➡️ Стартуем тему массивов и Хэш-таблиц #array #hash

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

🟢Easy
1331. Rank Transform of an Array

Company: 📱🔍

📝Дан массив целых чисел, замените каждый элемент его рангом.

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

💡: используйте дополнительный массив для сортировки

#leetcode1331 | #easy #array #hash

🟢Easy
219. Contains Duplicate II

Company: 🔍📱❤️

📝Дан массив целых чисел nums и целое число k.

Вернуть true, если в массиве есть два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k

💡: поддерживайте set размером k

#leetcode219 | #easy #array #hash

🟡Medium
532. K-diff Pairs in an Array

Company: 🔍📱🚖

📝Дан массив целых чисел nums и целое число k, верните количество уникальных пар k-diff в массиве.

Пара k-diff — это пара (nums[i], nums[j]), для которой верны следующие условия:
➖0 <= i, j < nums.length
➖i != j
➖abs(nums[i] - nums[j]) == k

💡: для поиска уникальных пар перебирайте ключи HashMap

#leetcode532 | #medium #array #hash

🟡Medium
1711. Count Good Meals

Company: 🔍

📝Дан массив целых чисел, вернуть количество пар элементов, сумма которых равна степени двойки.

Вернуть результат по модулю (10⁹ + 7)

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

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

💡: для каждого элемента примените идею TwoSum, где target будет равен всем степеням двойки из условия

#leetcode1711 | #medium #array #hash

🟡Medium
3185. Count Pairs That Form a Complete Day II

Company: 📱

📝Дан целочисленный массив hours, представляющий время в часах, вернуть количество пар (i, j), где i < j и hours[i] + hours[j] образуют полный день.

Полный день определяется как продолжительность времени, кратная 24 часам

💡: для текущего элемента ищите необходимый остаток, чтобы дополнить его до числа кратного 24

#leetcode3185 | #medium #array #hash

🟡Medium
3371. Identify the Largest Outlier in an Array

Company: 📱🔍

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

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

Верните наибольший выброс из массива

💡: какой будет сумма массива, если удалить из нее выброс?

#leetcode3371 | #medium #array #hash

🟡Medium
3404. Count Special Subsequences

Company: 🔍

📝Дан массив nums, состоящий из положительных целых чисел.

Специальная подпоследовательность — это индексы (p, q, r, s), где p < q < r < s, которые удовлетворяют следующим условиям:
▫nums[p] * nums[r] == nums[q] * nums[s]
▫между каждой парой индексов должен быть хотя бы один элемент: q - p > 1, r - q > 1 и s - r > 1.

Верните количество различных специальных подпоследовательностей

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

7 <= nums.length <= 1000

💡: выберите начальную позицию r и от нее передвигайте все индексы, сохраняя нужные соотношения: (nums[s] / nums[r]) и (nums[p] / nums[q])

#leetcode3404 | #medium #array #hash

🖼Иллюстрация к решению задачи 3404

Расстановка и передвижение указателей (p, q, r, s)

#figure #array #hash

🔴Hard
2488. Count Subarrays With Median K

Company: 🔍

📝Вам дан массив размером n, состоящий из различных целых чисел от 1 до n, и положительное число k.

Верните количество непустых подмассивов, медиана которых равна k.

Медиана массива — это средний элемент после сортировки массива по возрастанию. Если массив имеет четную длину, медианой является левый средний элемент.

Например:

медиана [2,3,1,4] — 2
медиана [8,4,3,5,1] — 4

💡: ведите переменную баланса, которую будете увеличивать, если текущий элемент больше k и уменьшать, если меньше

#leetcode2488 | #hard #array #hash

🔴Hard
1224. Maximum Equal Frequency

Company: 🔍

📝Дан целочисленный массив.

Вернуть максимально возможную длину префикса, где после удаления ровно одного элемента все оставшиеся встречаются одинаковое количество раз

💡: вычисляйте длину префикса, который можно составить из частоты текущего элемента и количества чисел с данной частотой

#leetcode1224 | #hard #array #hash