题解 | #和为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
        # 题目保证“至少存在一个合法的连续子数组”，不需要处理找不到累加为k的情况
        # 记录每个元素的累加和以及第一次出现的位置
        sum_map = {0:-1} # 和为0的子数组长-1
        max_len = 0 # 最长连续子数组长
        cur_sum = 0 # 当前累加和

        for i, num in enumerate(arr):
            cur_sum += num 
            # 存在一个累加和加上当前值为k
            if cur_sum-k in sum_map:
                # 更新最长连续子数组长
                max_len = max(max_len, i-sum_map[cur_sum-k])

            # 更新当前累积和到记录表中
            if cur_sum not in sum_map:
                sum_map[cur_sum] = i
        return max_len