题解 | #NC-125未排序数组中累加和为给定值的最长子数组长度#
未排序数组中累加和为给定值的最长子数组长度
http://www.nowcoder.com/practice/704c8388a82e42e58b7f5751ec943a11
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;
}
}; 