NC125 和为K的连续最大子数组

给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ，求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。 [1,2,3]的连续子数组有[1,2]，[2,3]，[1,2,3] ，但是[1,3]不是

要求：空间复杂度 O(n)， 时间复杂度 O(n)

示例1 输入： [1,-2,1,1,1],0 返回值： 3

示例2 输入： [0,1,2,3],3 返回值： 3

---

前缀和+哈希表

哈希表记录前缀和第一次出现的位置

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max length of the subarray sum = k
     * @param arr int整型vector the array
     * @param k int整型 target
     * @return int整型
     */
    int maxlenEqualK(vector<int>& arr, int k) {
        // write code here
        unordered_map<int, int> mp;
        mp[0] = -1;
        int pre = 0, ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            pre += arr[i];
            if (mp.find(pre-k) != mp.end()) {
                ans = max(ans, i-mp[pre-k]);
            }
            if (mp.find(pre) == mp.end()) {
                mp[pre] = i;
            }
        }
        return ans;
    }
};