Я сталкивался с этим вопросом и везде, кроме пары мест, нашел решение, используя hashmap. Но решение для хэш-карты заканчивается, когда диапазон увеличивается. Ниже я нашел решение, в котором говорится, как использовать «Очередь приоритетов», чтобы уменьшить сложность пространства до O (n).
Основная идея состоит в том, чтобы инициализировать приоритетную очередь парами (a, a + 1) для a в диапазоне [1, N), а затем многократно увеличивать второе значение наименьшего (суммой кубы), пока не достигнет N. Если в любой момент два самых маленьких элемента в очереди равны, у вас есть решение.
Я не получил решение. Если мы увеличиваем второе значение до указанного диапазона, то сложность пространства снова будет равна O (n ^ 2), так же как и в hashmap. Может ли кто-нибудь предоставить код для решения этой проблемы, используя очередь приоритетов, которая использует пространство O (n)?