Порридж В Ко-ливинге
Задача сегодняшняя довольно легкая
Порридж В Ко-ливинге
Легче чем предыдущая, мне так показалась
Порридж В Ко-ливинге
Ну мне так показаллось
Порридж В Ко-ливинге
Там же обязательно за O(logN) надо было?
Порридж В Ко-ливинге
За N в теории не получалось же, из-за 100x100 матрицы
Viktor
Ага, всё так. Только за N*M
Viktor
строки и столбцы
Порридж В Ко-ливинге
Аааа
Viktor
Ну чё, учим Кобол?
Viktor
https://stackoverflow.blog/2020/04/20/brush-up-your-cobol-why-is-a-60-year-old-language-suddenly-in-demand/?cb=1
Viktor
Иван
О я писал на Коболе)
Иван
Язык кстати очень красиво структурирован
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Там еще всякие
Иван
И ещё читается как текст вообще
Порридж В Ко-ливинге
Помоему lisp
Порридж В Ко-ливинге
И еще какой-то
Порридж В Ко-ливинге
Ладно, молчу т.к. не помню
V
продолжаются медиум задачки )
Порридж В Ко-ливинге
Вот все эти челенджи – фигня перед одним
Порридж В Ко-ливинге
Решить нормально за один подход, не потртив на одну задачку 3-5 часов
Evgeniy
Мне кажется харды пойдут в самом конце только
Evgeniy
И конец этой
Evgeniy
Аж 4 подсказки у сегодняшней задачи
Порридж В Ко-ливинге
Думаете можно за O(N) решить?
Evgeniy
Ещё не смотрел их
Evgeniy
Надо подумать как
Viktor
Вроде, подобная задачка уже была, которая с балансами.
Viktor
Вот здесь аналогично можно действовать.
Порридж В Ко-ливинге
Да, тоже на баланс напоминает
Порридж В Ко-ливинге
Даже, кажется, если заморочить можно O(1) пямять и O(N) “скорость”
Evgeniy
Со скобками которая?
Viktor
воу-воу, а как O(1) по памяти 🤔
Порридж В Ко-ливинге
С O(1) нереально будет по скорости
Порридж В Ко-ливинге
Надо где-то координаты хранить
Порридж В Ко-ливинге
И префиксное значение суммы
Порридж В Ко-ливинге
Щас попробую реализовать
V
брутфорс сработал. это вообще законно так делать?
Порридж В Ко-ливинге
Написано про это
V
сейчас почитаю )
V
напоминает задачку про деление без деления
Evgeniy
Брутфорс и правда работает
Viktor
брутфорс сработал. это вообще законно так делать?
А что там за брутфорс у тебя? Там же можно за O(n^3), а можно улучшить до квадрата с помощью префиксных сумм.
Viktor
Они явно в первой подсказке пишут, что куб не должен работать. Я его даже писать не стал поэтому.
Evgeniy
n^2 брутфорс
Viktor
Если работает, то лол, конечно.
Порридж В Ко-ливинге
А что там за брутфорс у тебя? Там же можно за O(n^3), а можно улучшить до квадрата с помощью префиксных сумм.
О, у меня примерно такое и получилось(
Порридж В Ко-ливинге
Я думал будет быстрее n^2
Viktor
тройной цикл получается
Viktor
самый самый брутфорс если
Viktor
без префиксных сумм
Evgeniy
Один цикл сдвиг, с которого начинаем. Второй для набора суммы
Viktor
Я не совсем понял просто. У тебя вышло сделать O(n^2) и без дополнительной памяти?
Viktor
Или всё-таки за O(n^3)?
Evgeniy
public class Solution {
public int SubarraySum(int[] nums, int k) {
int len = nums.Length;
int count = 0;
for (int i = 0; i < len; i++) {
int sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
if (sum == k)
count++;
}
}
return count;
}
}
Evgeniy
Память только под сумму
Порридж В Ко-ливинге
Это победа неожиданностью
Viktor
public class Solution {
public int SubarraySum(int[] nums, int k) {
int len = nums.Length;
int count = 0;
for (int i = 0; i < len; i++) {
int sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
if (sum == k)
count++;
}
}
return count;
}
}
Да, классное решение. Спасибо. Действительно можно не хранить префиксные суммы.
Порридж В Ко-ливинге
Они наверное не думали что будет Брутфорс брутфорс
Порридж В Ко-ливинге
Да, классное решение. Спасибо. Действительно можно не хранить префиксные суммы.
Да, кажется префиксное решение отпадает
Evgeniy
Да, классное решение. Спасибо. Действительно можно не хранить префиксные суммы.
Да, их можно на лету вычислять
Viktor
Огонь.
Viktor
Viktor
Чтобы не было вот так