Evgeniy
https://leetcode.com/problems/subarray-sum-equals-k/discuss/591873/C-simple-solution-using-Dictionary-and-prefix-sum
Evgeniy
Вот ещё решение с помощью хэш таблицы
V
Evgeniy
да, у меня ровно то же самое
Только оно, конечно, медленное... На шарпе выдало 628 мс, а с хэшем 116 мс
Порридж В Ко-ливинге
Что-то мне не привычно с Плюсами...
Порридж В Ко-ливинге
Теперь выдает time exceeded
Порридж В Ко-ливинге
На 4ом тесте
Evgeniy
Какое решение?
Порридж В Ко-ливинге
Но на компе у меня он мнговенно проходит
Viktor
видимо while true без break стрельнул или типа того
Порридж В Ко-ливинге
[1] ,0
Evgeniy
А это крайний случай
Порридж В Ко-ливинге
У меня норм проходит, у них, 4ый тест, норм проходит
Evgeniy
У меня он тоже сразу не прошёл
Evgeniy
Должен
Порридж В Ко-ливинге
Но не time exceede
Порридж В Ко-ливинге
Щас я попробую вставить костыль 😹😹😹
Viktor
Лучше кинуть код, давай глянем. Чудес не бывает — где-то ошибка там есть.
Evgeniy
Да, согласен
Порридж В Ко-ливинге
Оооо
Порридж В Ко-ливинге
Меня посадят
Порридж В Ко-ливинге
Буду сидеть с маньяками и педовфилами в камере
Evgeniy
Жить будешь)
Viktor
У нас здесь меритократия и нет законов 😄
Порридж В Ко-ливинге
ООй, уговорили
Порридж В Ко-ливинге
Я уже переделал, и у меня кажется работает
Порридж В Ко-ливинге
Но вот кину проблемный
Порридж В Ко-ливинге
Он не рабочий
Порридж В Ко-ливинге
Т.е. случаи с k = 0 не правильно дает
Порридж В Ко-ливинге
https://pastebin.com/fv6c883s
Порридж В Ко-ливинге
Но это вам просто посмотреть
Порридж В Ко-ливинге
Я догадываюсь, что из-за 200000000 иттераций может говорить так
Порридж В Ко-ливинге
Но 4 теста проходит
Порридж В Ко-ливинге
+ я добавлял переменные lowest, highest, и он все-равно писал exceeded
Viktor
оу, ноу, зачем 🙁 есть же вектора 😄
Viktor
выделять массив из 40 миллионов интов, идея понятная, но такое себе занятие.
Порридж В Ко-ливинге
На CF постоянно вижу
Порридж В Ко-ливинге
Ну обычно больше 1 МБ не доходит
Порридж В Ко-ливинге
У меня 20
Порридж В Ко-ливинге
😹😹😹
Evgeniy
В общем ты решил обойти все встроенные возможности)
Evgeniy
Кстати, а почему не сдаёшь решения на Си?
Evgeniy
Может быть там оно пройдёт
Порридж В Ко-ливинге
Я типо плюсы учу 🤣🤣🤣
Порридж В Ко-ливинге
Короче через мапу попробую
Evgeniy
Да, верное решение
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Я не совсем понял
Evgeniy
Экономней по памяти будет
Порридж В Ко-ливинге
Как случаи с k = 0
Порридж В Ко-ливинге
Этот алгоритм обходит
Порридж В Ко-ливинге
А, он же одновременно и проверяет и вставляет
Порридж В Ко-ливинге
Понял
Evgeniy
да, на следующей итерации он найдёт вставленное значение
Порридж В Ко-ливинге
Кстати
Порридж В Ко-ливинге
Я еще не до конца разобрался в ordered и unordere setах
Порридж В Ко-ливинге
Какой лучше подходит для такой задачки? unordered?
Порридж В Ко-ливинге
Как я понял, в ordered, быстрее итерации делать
Evgeniy
я думаю здесь нужно unordered_map
Evgeniy
сортировка не нужна здесь
Порридж В Ко-ливинге
Ну я тоже так думаю, но как это работает ток
Evgeniy
ключ-значение
Порридж В Ко-ливинге
Т.е. в ордеред вставляется со скоростью logn&
Evgeniy
а в сете только значения
Порридж В Ко-ливинге
?
Evgeniy
ну или ключи
Viktor
Как я понял, в ordered, быстрее итерации делать
более того в unordered и нельзя делать никакие итерации, т.е. циклом не пройтись, только по ключам запросы делать
Порридж В Ко-ливинге
Это же вроде хэш
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Только в ручную можно будет итерировать, что медленнее
Viktor
Т.е. в ордеред вставляется со скоростью logn&
верно. в unordered амортизированный O(1), если считаем что вычисление хеша дешёвое и коллизии маловероятны.