【模拟】

  • 题目要求时间复杂度为O(n)，说明最多只能有一个for循环
  • 空间复杂度为O(n)，说明需要一个和arr长度一样的数组或字典
  • 定义数组ans，用来存放满足要求的子数组的长度
  • 字典用来存放前i个元素和及其索引
  • 当sum_[j]-sum_[i]==k的时候说明出现了和为k的子数组，此时只需要变换一下式子，sum_[j]-k==sum_[i]，当sum_[i]出现在dic中时，就说明第i+1个元素到第j个元素可以构成满足要求的子数组，此时将i-dic[sum_[i]]赋给ans[i]
  • 同时判断此时的sum_[j]是否在dic中，不在的话需要add
  • 值得注意的是，对于dic的初始值，或者说sum_初始值对应的索引有一定的要求，刚开始没给dic初始值，发现在示例二一直报错，观察后发现是它没将第一个元素算进去。当我们计算长度的时候都是从第i+1个元素算起，也就是j-dic[sum_[i]]，这是没有算第i个元素的，所以我们在计算长度的时候也就无法考虑到arr[0]这个元素，因为min(i)==0，所以是从1开始计算的。所以，我们需要给一个小于0的初始索引，让arr[0]可以被计算，所以有dic{0:-1}，这样就可以将arr[0]这个元素算进去了。这是一个容易出错的地方
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        ans=[0]*len(arr)
        sum_=0
        dic={0:-1}
        for i in range(len(arr)):
            sum_+=arr[i]
            if sum_-k in dic:
                ans[i]=i-dic[sum_-k]
            if sum_ not in dic:
                dic[sum_]=i
        return max(ans)