和为 K 的最长子数组 c++完整代码实现

以下是和为 K 的最长子数组的 C++ 代码实现：

#include <unordered_map>
#include <vector>

using namespace std;

int maxSubArrayLen(vector<int>& nums, int k) {
    int n = nums.size();
    unordered_map<int, int> mp;
    int sum = 0, maxLen = 0;
    mp[0] = -1;
    for (int i = 0; i < n; ++i) {
        sum += nums[i];
        if (mp.count(sum - k)) {
            maxLen = max(maxLen, i - mp[sum - k]);
        }
        if (!mp.count(sum)) {
            mp[sum] = i;
        }
    }
    return maxLen;
}

该算法使用了前缀和和哈希表，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。具体实现细节如下：

1. 首先定义一个 unordered_map，用于存储前缀和与其下标对应的映射关系。
2. 初始化前缀和为 0，最大子数组长度为 0，将前缀和为 0 的下标设为 -1，遍历整个数组。
3. 每次遍历到一个数时，将其加到前缀和中，并判断是否存在前缀和为 sum - k 的数，如果存在，说明从该数到前面某个数之间的子数组和为 k，更新最大子数组长度。
4. 如果当前前缀和不在哈希表中，将其加入哈希表中。
5. 遍历结束后，返回最大子数组长度。