Самый длинный подмассив, сумма которого делится на K, с не более чем одним отрицанием II | Матема...

LeetCode 4064 - Самый длинный подмассив, делящийся на K, с не более чем одним отрицанием II | Еженедельный конкурс 192 В этом видео мы решаем задачу LeetCode 4064: Самый длинный подмассив, делящийся на K, с не более чем одним отрицанием II из Еженедельного конкурса 192. Это более сложная версия предыдущей задачи. Здесь n может достигать 1e5, а k — 3000, поэтому решения со сложностью O(N²) и O(N * K) слишком медленные. Ключевое наблюдение связано с префиксными суммами и модульной арифметикой. Для подмассива (l, r]: сумма = p[r] - p[l] Если мы инвертируем nums[j], где j находится внутри подмассива, новая сумма становится: новая сумма = p[r] - p[l] - 2 * nums[j] Чтобы новая сумма делилась на k: p[r] % k = (p[l] % k + (2 * nums[j]) % k) % k Таким образом, мы можем рассуждать в терминах: остаток справа = остаток слева + остаток при изменении Для каждого остатка мы храним: первую позицию префикса, где он появляется последнюю позицию префикса, где он появляется Мы также группируем индексы по: d = (2 * nums[j]) % k Затем для каждой возможной пары: остаток слева x остаток при изменении d мы вычисляем: требуемый остаток = (x + d) % k Используя самый ранний левый префикс и Для проверки наличия в выбранном подмассиве некоторого индекса j с остатком от деления d на 1000. Если да, то этот подмассив действителен. Временная сложность: O(N + K² log N) Пространственная сложность: O(N + K) #leetcode #leetcode4064 #biweeklycontest192 #prefixsum #modulararithmetic #binarysearch #competitiveprogramming #algorithms