和为K的连续子数组

class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        sum_index_map = {0:-1}
        sum = 0
        max = 0
        for i in range(0,len(arr)):
            sum = sum + arr[i]
            if (sum - k) in sum_index_map:
                l = i - sum_index_map[sum - k]
                if max < l:
                    max = l
            else:
                if sum not in sum_index_map:
                    sum_index_map[sum] = i
        return max

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        if len(arr) == 0:
            return 0
             
        dp = [0 for i in range(len(arr))]
        dp[0] = arr[0]

        # 初始化一个前缀和数列
        for i in range(1, len(dp)):
            dp[i] = dp[i-1] + arr[i]

        m = {}
        m[0] = [-1]
        # 记录前缀和出现的位置
        for i in range(len(dp)):
            if dp[i] in m:
                m[dp[i]].append(i)
            else:
                m[dp[i]] = [i]
        
        # 寻找前缀和减去目标值，得到需要寻找的前缀和
        max_n = 0
        for i in range(len(dp)):
            target_n = dp[i] - k

            if target_n not in m:
                continue

            target_arr = m[target_n]
            for target_index in target_arr:
                if target_index > i:
                    continue
                
                max_n = max(max_n, i-target_index)
        return max_n