Python | LeetCode
Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
👨💻 Алгоритм:
1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.
2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.
3⃣Возврат результата
Верните значение longestSubarray.
😎 Решение:
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
prefixSum = 0
longestSubarray = 0
indices = {}
for i, num in enumerate(nums):
prefixSum += num
if prefixSum == k:
longestSubarray = i + 1
if prefixSum - k in indices:
longestSubarray = max(longestSubarray, i - indices[prefixSum - k])
if prefixSum not in indices:
indices[prefixSum] = i
return longestSubarray
Ставь 👍 и забирай 📚 Базу знаний
5 · 797 ·