Задача: 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.

😎 Решение:
#include
#include

class Solution {
public:
int maxSubArrayLen(std::vector& nums, int k) {
int prefixSum = 0;
int longestSubarray = 0;
std::unordered_map indices;

for (int i = 0; i < nums.size(); ++i) {
prefixSum += nums[i];

if (prefixSum == k) {
longestSubarray = i + 1;
}
if (indices.find(prefixSum - k) != indices.end()) {
longestSubarray = std::max(longestSubarray, i - indices[prefixSum - k]);
}
if (indices.find(prefixSum) == indices.end()) {
indices[prefixSum] = i;
}
}

return longestSubarray;
}
};

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