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

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
        // 两个位置前缀和之差为 k 时，位置下标相减就是子数组长度。
        // 用前缀和的思想，但是这次不用数组存前缀和，用哈希表存某个前缀和第一次出现的位置。
        // 如果前缀和用数组存，两个下标是 i 和 j，双重循环的话时间复杂度太高，会超时。
        // 换成哈希表意思是算出一个前缀和往前找一次，同时更新一次最大长度。
        // 数组里有负数，可能会出现两个位置的前缀和相同的情况，这时只存第一次出现这个前缀和的下标。
        int n = arr.size();
        int currentSum = 0;
        int maxLength = 0;        
        unordered_map<int, int> prefixSumIndex;
        prefixSumIndex[0] = -1;
        for (int i = 0; i < n; ++i) {
            currentSum += arr[i];

            // 检查是否有前缀和等于 currentSum - k
            if (prefixSumIndex.count(currentSum - k)) {
                maxLength = max(maxLength, i - prefixSumIndex[currentSum - k]);
            }

            // 只记录前缀和第一次出现的位置
            if (!prefixSumIndex.count(currentSum)) {
                prefixSumIndex[currentSum] = i;
            }
        }

        return maxLength;
    }
};