题解 | 和为K的连续子数组

#include <unordered_map>
class Solution {
    /*
        一个数组存每位的前缀和，转换成两个数只差等于目标数，一个哈希表记录前缀和最先出现的位置，
        从后向前遍历前缀和数组，查找哈希表中的前缀和，维护最大长度即可
    */
public:
    int maxlenEqualK(vector<int>& arr, int k) {
        if(arr.empty())return 0;

        unordered_map<int , int> mp;  //前缀和-下标
        vector<int> preSum(arr.size()+1);  //最后应该包括进去

        preSum[0] = 0;  //头一个下标
        mp[0] = 0;

        for(int i=1; i<preSum.size(); i++){
            preSum[i] = arr[i-1] + preSum[i-1];  //初始化前缀数组，本位前缀不包括本位数；
            if(mp.find(preSum[i]) == mp.end()){  //只更新最先出现的前缀和，没有则添加
                mp[preSum[i]] = i;
            }
        }
        
        int maxlen = 0;
        for(int i=preSum.size()-1; i>=0; i--){
            int partner = preSum[i] - k;

            if(mp.find(partner) != mp.end()){  //如果找到了，则看是不是最大
                maxlen = max(maxlen, i-mp[partner]);
            }
        }

        return maxlen;
    }
};