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

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; // 踩坑 哈希表的key=0处要初始化为-1
                        // 这是因为当preSum==k时，说明数组从0直到当前位置的所有元素累加和为k，
                        // 此时preSum-k==0，-1保证了第一个元素也被计入总长度
        int maxLen = 0;
        int preSum = arr[0];
        hashMap[arr[0]] = 0; // initialize
        for(int i = 1; i < arr.size(); i++){ // i从0或1开始都一样
            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;
           
    }
};