4. Решаем LeetCode на Java и попадаем в топ по времени
11 июля 2026 г.
Я не люблю джаву, да и литкодные интервью не очень люблю, так что совершенно непонятно, как и зачем я вписался в решение ежедневных литкодных задач на джаве. Но раз уж я это делаю уже больше полугода, то у меня есть чем поделиться.
К своим настоящим интервью я обычно готовился либо на чистом C, либо на C++ с STL. Оба отлично подходят для стандартных литкодных задач, и все свои офферы я успешно получил, проходя интервью на C/C++. Я знаю людей, которые собеседовались на джаве, и мне всегда было не очень понятно, зачем: язык достаточно многословный, для простых вещей типа сортировки массива по убыванию нужно помнить, как пишутся всякие странные вещи типа Collections.reverseOrder(), и прочее такое.
Но, так или иначе, я нашёл себя в этой странной ситуации, решая ежедневные задачки на джаве. А литкод при сабмите решения показывает гистограмму, как моё решение сравнивается по времени работы с другими решениями на этом языке:
И пусть это ни на что не влияет — но всё равно хочется получать результат получше. После полугода ежедневных задач я, кажется, немного разобрался в том, как уменьшить время выполнения решения литкодной задачи на джаве.
Важное замечание: я почти ничего, или совсем ничего, не знаю про оптимизацию кода на джаве вне литкода. Всё, что я пишу ниже, относится к исполнению кода на литкоде и нигде более. Я предупредил!
Начнём с перечисления простых идей, а потом посмотрим, к чему они приводят.
Избегаем аллокаций
Аллокации — это дорого. Понятно, что без них обычно не обойтись: как минимум, нужно создать какой-нибудь new int[n] в начале вашей функции. Но если вызывать new в цикле, то вы, скорее всего, окажетесь где-нибудь в середине гистограммы, если только эти аллокации не являются абсолютно необходимыми для решения.
Избегаем wrapper types
В джаве нельзя просто так создать коллекцию из примитивных типов, что-нибудь вроде ArrayList<int>; вместо этого нужно делать ArrayList<Integer>. Я подозреваю, что это совершенно не проблема для реального кода, потому что мало кому в настоящей программе может понадобиться контейнер из примитивных типов, но конкретно в контексте литкодных задач они нужны довольно часто, и это большая проблема. Каждый Integer — это объект, который требует аллокации, так что если new int[n] выделяет память один раз, то если вы сделаете new ArrayList<Integer>() и потом добавите туда n элементов, то получится n+1 аллокация, и в топ по времени вы, скорее всего, не попадёте.
Из этих двух идей следует третья:
Избегаем коллекций
Да, все вот эти HashSetы и TreeMapы мы использовать не будем. Иногда без них не обойтись, но очень часто можно избежать их использования. Контейнеры типа HashMap<Integer, Integer> просто сочетают в себе всё плохое из предыдущих абзацев.
Разбавим негатив позитивной мыслью:
Вызовы функций дешёвые
На литкоде я пока не видел ситуации, где время бы сильно улучшилось от уменьшения количества вызовов функций. Никаких проблем нет выделить часть логики в функцию и вызывать её, или писать рекурсивную реализацию обхода в глубину. Короче говоря, вызывать функции не бойтесь.
Обращение к элементам массива дорогое
Без обращения к элементам массива, конечно, не обойтись, но если вам нужно читать один и тот же элемент несколько раз, то лучше бы сохранить его значение в переменную. Я совершенно не уверен, что эта рекомендация имеет какой-либо смысл вне литкода, но конкретно на литкоде — да, это ускоряет код.
Что же мы получаем, если мы пытаемся решать задачу, следуя этим правилам? Получаем интересное правило:
Если вы хотите написать быстрое решение литкодной задачи на джаве, пишите его так, как будто это чистый C.
И действительно: большинство моих решений могут быть переписаны на C с минимальными изменениями.
— Но что же делать, если для решения задачи нужны всякие там алгоритмы и структуры данных?
— Да просто берём и реализуем их руками.
Для любого настоящего интервью это совет так себе: вряд ли интервьюер будет сильно рад, если вы вместо использования стандартного HashSet пойдёте писать свою реализацию. Но мы же решаем задачки просто так, так что почему бы и нет? Это вовсе не так сложно. Давайте я покажу несколько примеров.
Заменяем HashSet и HashMap на простое линейное зондирование
На литкоде очень много задач, которые решаются использованием HashSet или HashMap, чтобы получить поиск за амортизированное константное время. Очень часто вам нужен HashSet<Integer> или HashMap<Integer, Integer>, и они оба нарушают все перечисленные выше принципы.
К счастью, есть очень простой трюк, который позволяет выбросить из вашего кода эти контейнеры, и этот трюк мы использовали ещё в начале 2000-х на контестах ACM, когда мы решали там задачи на Borland Pascal 7.0 и Borland C++ 3.1. Простая хэш-функция и линейное зондирование — это самый простой способ сделать hash set или hash map для примитивных типов, и он не требует аллокаций, помимо выделения памяти для массивов в самом начале.
Для целых чисел я обычно использую хэш-функцию, адаптированную из вот этого ответа на StackOverflow; в джаве нет unsigned int, так что приходится использовать Math.floorMod:
public int hash(int x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return Math.floorMod(x, size);
}
Для строк отлично подходит вот такая несложная хэш-функция:
public int hash(char[] s) {
int result = 0;
for (char c : s) {
result = result * 37 + c;
}
return Math.floorMod(result, size);
}
Мой опыт с литкодом показывает, что зачастую выгоднее сразу перевести строки в массив char[] или byte[], вызвав .toCharArray() или .getBytes(). Это аллокация, но почему-то это получается быстрее, чем постоянно вызывать .charAt().
Что же мы делаем с этими хэш-функциями? Давайте посмотрим на задачу №1, Two Sum — отличный пример простой задачи на hash maps, которую можно решить с использованием HashSet за амортизированное линейное время. Обычно она решается как-то так:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; ++i) {
int needed = target - nums[i];
Integer got = map.get(needed);
if (got != null) {
result[0] = i;
result[1] = got;
break;
}
map.put(nums[i], i);
}
return result;
}
}
Это решение выполняется за 2мс. Давайте перепишем его с использованием нашей хэш-функции и линейного зондирования. Нам понадобятся два массива: один для ключей и один для значений.
int size;
int[] keys;
int[] values;
Будем использовать хэш-функцию для int, описанную выше. Чтобы положить пару «ключ — значение» в нашу таблицу, используем линейное зондирование: перебираем все элементы наших массивов в цикле по кругу, начиная с хэш-кода ключа, пока мы либо не найдём такой же ключ, либо не увидим пустую ячейку:
void put(int key, int value) {
int code = hash(key);
int k = keys[code];
int v = values[code];
while (v != 0 && key != k) {
code = (code + 1) % size;
k = keys[code];
v = values[code];
}
keys[code] = key;
// значения — [0..n); добавляем 1, чтобы 0 означал «свободно»
values[code] = value + 1;
}
Чтение значения из таблицы очень похоже:
int get(int key) {
int code = hash(key);
int k = keys[code];
int v = values[code];
while (v != 0 && key != k) {
code = (code + 1) % size;
k = keys[code];
v = values[code];
}
return v - 1; // -1 означает «не найдено»
}
Перед использованием таблицы нужно создать массивы:
void init(int sz) {
size = sz;
keys = new int[size];
values = new int[size];
}
С использованием этой хэш-таблицы решение будет выглядеть очень похоже на решение с HashMap. Чтобы линейное зондирование было эффективным, очень желательно, чтобы таблица никогда не заполнялась более чем на 50%, так что мы выделим массивы в два раза больше необходимого. Всё остальное очень похоже:
public int[] twoSum(int[] nums, int target) {
init(nums.length * 2 + 1);
int[] result = new int[2];
for (int i = 0; i < nums.length; ++i) {
int needed = target - nums[i];
int got = get(needed);
if (got != -1) {
result[0] = i;
result[1] = got;
break;
}
put(nums[i], i);
}
return result;
}
И это решение даёт 1мс! Само собой, разница между 1мс и 2мс не такая уж и принципиальная, но на задачах, где тесты побольше, разница может быть заметнее.
В зависимости от того, какие у вас данные, возможны ли нулевые ключи или значения или нет и т.п., вам может понадобиться немного изменить логику, например, там, где я добавляю 1 для сохранения нулевых значений.
Храним графы в виде массивов
Графы на литкоде зачастую задаются в виде массива рёбер int[][] edges, где каждый элемент edge задаёт одно ребро от edge[0] до edge[1], которое может быть направленным или нет в зависимости от задачи.
Обычно предполагается, что вы переложите этот граф во что-нибудь вроде ArrayList<ArrayList<Integer>>, сохраняя для каждой вершины список смежных с ней вершин. Но это очень много аллокаций! Так что мы лучше воспользуемся массивами:
int[] graph = new int[2 * edges.length];
int[] degree = new int[n];
int[] offset = new int[n];
Сначала посчитаем степень каждой вершины:
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
++degree[from];
++degree[to];
}
Теперь вычислим смещение в массиве для каждой вершины, суммируя степени:
int sumDegree = 0;
for (int i = 0; i < n; ++i) {
offset[i] = sumDegree;
sumDegree += degree[i];
}
Наконец, ещё раз переберём все рёбра, на этот раз сохраняя список смежных вершин в массиве. Понадобится временный массив для подсчёта смежных вершин:
int[] counts = new int[n];
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
graph[offset[from] + counts[from]++] = to;
graph[offset[to] + counts[to]++] = from;
}
Теперь, когда граф представлен в таком виде, его очень просто обойти. Вот, например, обход в ширину:
boolean[] visited = new boolean[n];
int[] queue = new int[n];
int r = 0, w = 0;
queue[w++] = start;
visited[start] = true;
while (r < w) {
int curr = queue[r++];
int itsOffset = offset[curr];
int itsDegree = degree[curr];
for (int i = 0; i < itsDegree; ++i) {
int to = graph[itsOffset + i];
if (!visited[to]) {
visited[to] = true;
queue[w++] = to;
}
}
}
Сортируем массивы вручную
Я серьёзно! Просто напишите свою любимую сортировку — быструю или пирамидальную. Заодно можно будет добавить к ней сохранение изначальных позиций элементов, если это нужно для задачи. Я нередко замечал, что моя сортировка работает быстрее, чем Arrays.sort или Collections.sort.
void quicksort(int[] arr, int l, int r) {
// берём среднее arr[l] и arr[r] в качестве опорного,
// чтобы уменьшить вероятность попасть на плохой тест
int pivot = arr[l] + ((arr[r] - arr[l]) >> 1);
int i = l, j = r;
while (i <= j) {
while (arr[i] < pivot) ++i;
while (arr[j] > pivot) --j;
if (i <= j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
++i;
--j;
}
}
if (l < j) quicksort(arr, l, j);
if (i < r) quicksort(arr, i, r);
}
Я пользуюсь этими правилами в своих решениях на джаве и чаще всего обгоняю 90% решений, а иногда и больше. Есть и исключения: например, префиксное дерево (trie), похоже, лучше реализовывать с аллокациями, а не на массиве — вероятно, потому что огромный массив не влазит в кэш. В общем, попробуйте и посмотрите сами, что вам нравится и для вас работает, а что нет.
Ну а главное — не используйте ничего из описанного на настоящем интервью. Серьёзно, не надо.