题解 | #哈希+前缀和系列#

专题系列

https://leetcode-cn.com/problems/find-longest-subarray-lcci/solution/qian-zhui-he-ha-xi-by-louris-10h7/

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
        int n = arr.size();
        unordered_map<int, int> ump;
        ump[0] = -1;
        int ans = 0;
        int sum = 0;
        for(int i = 0 ; i < n; i ++){
            sum += arr[i];
            if(ump.find(sum - k) != ump.end()){
                ans = max(ans, i - ump[sum - k]);
            }
            if(ump.find(sum) == ump.end()) ump[sum] = i; //如果不存在，则更新，保证同一个前缀sum记录的是最小的索引
        }
        return ans;
    }
};