Я полагаю, вы уже прочитали описание.
Сначала я сделаю это своим невежественным способом или грубой силой, если мы используем правильный термин. Затем мы просмотрим обсуждение в поисках вдохновения.
Итак, для нашей функции мы получим
1. s: массив чисел
2. d: целевая сумма, которую мы хотим сложить
3. m : сколько чисел мы должны сложить
и, наконец, мы должны вернуть количество возможных комбинаций, которые мы нашли в массиве.
[constraints] n = s.length 1 <= n <= 100 1 <= s[i] <= 5, where (0 <= i < n) 1 <= d <= 31 1 <= m <= 12
Вот мое решение:
1. создать переменную для подсчета количества возможных комбинаций, которые мы находим
2. выполнить цикл по массиву чисел, но остановиться, когда в массиве окажется недостаточно чисел, чтобы удовлетворить m(количество чисел, которое мы должно сложиться). Например, остановиться, когда в массиве останется 2 числа, а для суммы нужно 3 числа.
3. Используйте Array.slice()
, чтобы получить подмассив: s[i], s[i+1], … s[i+m — 1]
4. Используйте Array.reduce()
, чтобы получить сумму подмассив
5. проверьте, является ли сумма подмассива тем, что мы ищем. Если да, count ++
.
6. вернуть count
Затем я увидел в обсуждении то, что видел раньше, но на что особо не обращал внимания: скользящее окно, которое, вероятно, использовал бы для этой задачи опытный хакер (а может и нет?).
По сути, этот алгоритм помогает уменьшить временную сложность до линейной временной сложности. Это кажется менее сложным, чем я себе представлял. В Интернете есть несколько версий скользящего окна, которые немного отличаются, но их основная концепция одинакова. Я покажу один здесь.
Скажем, у нас есть массив [6,12,1,31,25,73,12]
, и мы хотим найти наибольшую сумму с тремя соседними числами, в данном случае 129 (31+25+73
). С помощью скользящего окна мы не будем продолжать складывать подмассивы, проверяя сумму [6,12,1]
, затем [12,1,31]
, затем [1,31,25]
, как я сделал с Array.reduce()
. Вместо этого мы будем отслеживать наибольшую сумму, добавляя следующее значение и удаляя предыдущее. После проверки суммы (19
) из [6, 12, 1]
мы вычитаем 6
, добавляем 31
и получаем 44
. Затем мы вычитаем 12
, добавляем 25
и получаем 57
. Таким образом, это приведет к линейной временной сложности.
Это будет выглядеть так.
[6,12,1,31,25,73,12]
[6,12,1,31,25,73,12]
[6,12,1,31,25,73,12]
[6,12,1,31,25,73,12]
[6,12,1,31,25,73,12]
Итак, давайте реализуем скользящее окно в нашем решении.
Это все на сегодня.