#java #algorithm
#java #алгоритм
Вопрос:
У меня есть массив чисел, теперь я хочу найти все последовательные суммы подмассивов, значение которых соответствует значению, меньшему или равному k. Я хочу вернуть наибольший размер подмассива.
Это моя программа:
public static int process(List<Integer> arr, int k) {
int size = 0;
for (int i = 0; i < arr.size(); i ) {
int sum = 0;
for (int j = i; j < arr.size(); j ) {
sum = arr.get(j);
if (sum <= k) {
size = Math.max(size, j - i 1);
}
}
}
return size;
}
ограничения:
arr size is between 1 to 100000
array elements are between 1 to 100
k is between 1 to 1000000
Объяснение:
Arrays.asList(2, 3, 5, 1, 1, 2, 1), 7
arr = 2, 3, 5, 1, 1, 2, 1
k= 7
возможные подмассивы:
[2], [3], [5], [1], [1], [2], [1]
[2,3], [5,1], [1,1], [1,2], [2,1]
[5,1,1], [1,1,2], [1,2,1]
[1,1,2,1]
Maximum sub array is [1,1,2,1] = its length is 4. So program should return 4.
Я получил эту задачу на конкурсном экзамене на прошлой неделе, когда я использовал этот код, он прошел только 50% тестовых случаев. Это не удалось для некоторых скрытых тестовых примеров, указывающих на неправильный вывод, а в некоторых тестовых примерах указано время ожидания.
В чем проблема с моим кодом?
Обновление: немного изменил мой код. И добавлен примерный пример.
Комментарии:
1. Можете ли вы объяснить свой вопрос и желаемый результат немного подробнее
2. Вы должны возвращать 0, когда ни один из подмассивов не добавляется к
k?3. @Hades, извините, что я пропустил их добавление, позвольте мне снова изменить вопрос
4. Причина тайм-аута в том, что ваш алгоритм равен O (n ^ 2). Вы могли бы немного ускорить его, разорвав внутренний цикл, как только сумма будет больше
k. Вы могли бы значительно ускорить его, используя скользящее окно.5. Вероятно, ваша проблема в том, что вы продолжаете работать, когда
sum > k. Или, по крайней мере, его часть. Вы должны смотреть вперед только доiтех пор, пока совокупная сумма оттуда не превысит сумму, к которой вы стремились.
Ответ №1:
Вложенные циклы означают, что производительность равна O (n 2). Вам нужно переосмыслить алгоритм.
Ниже приведено решение O (n), которое я покажу на примере. Написание кода по-прежнему является вашей задачей.
Что нам нужно, так это способ узнать сумму значений перед определенным индексом. С этим мы можем вычислить sumRange(i, j) = sumBefore(j) - sumBefore(i) .
Поскольку мы ищем sumRange(i, j) = k , нам нужно проверить, есть ли у нас sumBefore(i) = sumBefore(j) - k . Если мы это сделаем, у нас будет диапазон кандидатов с size = j - i .
Итак, повторите значения и вычислите накопленную сумму. Постройте Map из accSum indexAfter значения, ведущего к этой накопленной сумме.
Скажем, массив равен [1, 6, 5, 3, 2, 8, 4, 2, 7, 1] и k = 13 :
Index: 0 1 2 3 4 5 6 7 8 9
Value: 1 6 5 3 2 8 4 2 7 1
accSum: 0 1 7 12 15 17 25 29 31 38 39 sumBefore
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
indexAfter: 0 1 2 3 4 5 6 7 8 9 10 index
Добавление фиктивного 0 → 0 сопоставления просто упрощает логику вашего кода.
По мере выполнения итерации у вас есть накопленная сумма до настоящего времени включительно, т. Е. sumBefore(i 1) Поэтому Посмотрите, есть ли у нас диапазон, т. Е. sumBefore(x) = sumBefore(i 1) - k = accSum - k Поэтому Посмотрите на карте accSum - k , и если найдено, значение равно x , что означает, что у нас есть диапазон кандидатов x, i 1 .
Я надеюсь, что все это имело смысл.
Обновить
Вопрос был изменен для поиска сумм <= k , а не только сумм, точно равных k .
Это легко сделать с помощью приведенной выше логики, изменив значение Map на a TreeMap , или, точнее, a NavigableMap , и заменив get() вызов ceilingEntry() вызовом:
Возвращает сопоставление ключ-значение, связанное с наименьшим ключом, большим или равным данному ключу, или
nullесли такого ключа нет.
Если возвращаемый ключ (сумма) больше параметра, результатом является сумма подмассива, которая меньше k .