Хеш-таблицы представляют собой чрезвычайно полезную структуру данных, поскольку поиск в среднем занимает ожидаемое время O (1), то есть объем работы, выполняемой хеш-таблицей для выполнения поиска, в лучшем случае является константой. Некоторые проблемы, связанные со структурой данных и алгоритмами, могут быть очень эффективно решены с помощью хеширования, которые в противном случае имеют высокую временную сложность.

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

  • std::set, std::map, std::unordered_set, std::unordered_map in C++
  • HashMap, HashSet, TreeMap в Java
  • Dictionary, Set в Python
  1. Найти пару с заданной суммой в массиве
  2. Проверить, существует ли подмассив с нулевой суммой
  3. Вывести все подмассивы с нулевой суммой
  4. Найти самую длинную подпоследовательность, состоящую из последовательных целых чисел
  5. Найти дубликаты в заданном диапазоне k в массиве
  6. Подсчитать различные абсолютные значения в отсортированном массиве
  7. Найти подмассив по заданной сумме в заданном массиве целых чисел
  8. Найти наибольший подмассив, состоящий из последовательных целых чисел
  9. Найти повторяющийся элемент в массиве с ограниченным диапазоном
  10. Найти подмассив максимальной длины, имеющий одинаковое количество нулей и единиц
  11. Найти подмассив максимальной длины по заданной сумме
  12. Найти мажоритарный элемент в массиве (алгоритм большинства голосов Бойера – Мура)
  13. Пользовательская сортировка | Сортировать массив на основе другого массива
  14. Пользовательская сортировка | Сортировать элементы по их частоте и индексу
  15. Эффективная сортировка массива с множеством повторяющихся значений
  16. Рассчитать частоту всех элементов, присутствующих в массиве указанного диапазона, в линейное время и с использованием постоянного пространства
  17. Заменить каждый элемент массива на его соответствующий ранг
  18. Группировать элементы массива по первому вхождению
  19. Найти все симметричные пары в массиве пар
  20. Построить самый длинный палиндром путем перемешивания или удаления символов из строки
  21. Найти количество различных элементов в каждом подмассиве размера k
  22. Распечатать все подмассивы массива, имеющего отдельные элементы
  23. Найти минимальный индекс повторяющегося элемента в массиве
  24. Найти индекс максимального встречающегося элемента с равной вероятностью
  25. Проверить, сформирован ли массив последовательными целыми числами
  26. Найти две неперекрывающиеся пары с одинаковой суммой в массиве
  27. Найти подмассивы с заданной суммой в массиве
  28. Проблема с 3 разделами
  29. Найти два нечетно встречающихся элемента в массиве, не используя лишнего места
  30. Найти пары с заданной разностью k в массиве
  31. Найти нечетно встречающийся элемент в массиве за один проход
  32. Определить, равны ли два целых числа без использования операторов сравнения и арифметических операций
  33. Задача на 4 суммы | Четверки с заданной суммой
  34. Найти триплет с заданной суммой в массиве
  35. Найти количество превосходящих для каждого элемента массива
  36. Построить двоичное дерево по порядку и порядку уровней
  37. Построить двоичное дерево из обходов inorder и postorder
  38. Построить бинарное дерево из обхода по порядку и по предзаказу
  39. Клонировать двоичное дерево со случайными указателями
  40. Эффективно распечатайте все узлы между двумя заданными уровнями в двоичном дереве
  41. Найти предварительный обход двоичного дерева по его порядку и послепорядку
  42. Печать правого вида двоичного дерева
  43. Найти обход двоичного дерева по порядку и по порядку следования двоичного дерева
  44. Итеративно выводить путь от листа к корневому для каждого листового узла в двоичном дереве
  45. Найти пару с заданной суммой в BST
  46. Найти максимальную ширину заданного двоичного дерева
  47. Построить двоичное дерево из заданного родительского массива
  48. Найти диагональную сумму заданного двоичного дерева
  49. Печать диагонального обхода двоичного дерева
  50. Выполнить вертикальный обход бинарного дерева
  51. Найти вертикальную сумму в заданном двоичном дереве
  52. Найти предков данного узла в двоичном дереве
  53. Печать двоичного дерева сверху
  54. Печать двоичного дерева снизу
  55. Печать бинарного дерева слева
  56. Вывести все узлы идеального двоичного дерева в определенном порядке
  57. Обход двоичного дерева в обратном порядке
  58. Обход двоичного дерева по спирали
  59. Обход двоичного дерева с порядком уровней
  60. Построить двоичное дерево из матрицы предков
  61. Найти вероятность того, что человек жив после N шагов на острове
  62. Узлы ссылок присутствуют на каждом уровне двоичного дерева в виде связанного списка
  63. Преобразование двоичного дерева в двусвязный список по спирали
  64. Удалять дубликаты из связанного списка за один проход
  65. Определить цикл в связанном списке (алгоритм определения цикла Флойда)
  66. Клонировать связанный список со случайными указателями
  67. Найти все общие элементы, присутствующие в каждой строке данной матрицы
  68. Сгенерировать список возможных слов из символьной матрицы
  69. Найти общие элементы, присутствующие во всех строках матрицы
  70. Найти повторяющиеся строки в двоичной матрице
  71. Найти все слова из данного списка, которые следуют тому же порядку символов, что и заданный образец
  72. Найти все возможные комбинации, заменив заданные цифры на символы из соответствующего списка
  73. Изоморфные струны
  74. Определить, являются ли две строки анаграммой или нет
  75. Проверить, присутствует ли в строке повторяющаяся подпоследовательность

Спасибо за чтение.