题解 | #NC125-未排序数组中累加和为给定值的最长子数组长度#

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> hashMap;
        hashMap[0] = -1; // 踩坑 这里的哈希表要初始化，否则出错
        int maxLen = 0;
        int preSum = arr[0];
        hashMap[arr[0]] = 0; // initialize
        for(int i = 1; i < arr.size(); i++){ // i也可以直接从0开始
            preSum += arr[i];
            if(hashMap.find(preSum) == hashMap.end())
                hashMap[preSum] = i; // 只加入第一个未出现过的preSum
            if(hashMap.find(preSum-k) != hashMap.end())
                maxLen = max(maxLen, i-hashMap[preSum-k]);
        }
         return maxLen;
           
    }
};