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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max length of the subarray sum = k
# @param arr int整型一维数组 the array
# @param k int整型 target
# @return int整型
#
class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        # write code here
        # map维护的是前缀和，索引。前缀和相等时，取最小索引
        # 如果k=全部元素相加，需要一个初始和0，和位置-1
        map = {0: -1}
        presum = 0
        res = 0

        # 遍历较大数，寻找较小数的索引
        for i in range(len(arr)):
            presum += arr[i]
            
            if presum - k in map:
                tmp =  i - map[presum - k]
                res = max(tmp, res)

            map[presum] = map.get(presum, i)
        return res