Сложность: medium
Задача: 325. Maximum Size Subarray Sum Equals k

Дан целочисленный массив 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.

😎 Решение:

var maxSubArrayLen = function(nums, k) {
    let prefixSum = 0;
    let longestSubarray = 0;
    const indices = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        
        if (prefixSum === k) {
            longestSubarray = i + 1;
        }
        if (indices.has(prefixSum - k)) {
            longestSubarray = Math.max(longestSubarray, i - indices.get(prefixSum - k));
        }
        if (!indices.has(prefixSum)) {
            indices.set(prefixSum, i);
        }
    }
    
    return longestSubarray;
};

Ставь 👍 и забирай 📚 Базу знаний