Задача: 525. Contiguous Array
Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1.
Пример:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
👨💻 Алгоритм:
1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.
2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.
3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.
😊 Решение:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
countMap.put(0, -1);
int maxLength = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += (nums[i] == 1 ? 1 : -1);
if (countMap.containsKey(count)) {
maxLength = Math.max(maxLength, i - countMap.get(count));
} else {
countMap.put(count, i);
}
}
return maxLength;
}
}
👉Новости 👉Платформа