题解 | #未排序数组中累加和为给定值的最长子数组长度#

方法1：动态规划开二维数组超出内存限制了。。。

方法2：前缀和，同样超出内存限制了。。。

方法3：前缀和+哈希表，终于通过了

# 方法1，基于二维数组的dp，提交后只通过一个测试用例，原因是超出内存限制，测试用例中的数组arr太大了。。。
def run(arr,k):
    n=len(arr)
    res=-1

    # dp[i][j]: 以arr[i]为首，以arr[j]为尾的子数组的和
    dp=[[0 for _ in range(n)] for _ in range(n)]

    # 初始化第一行
    dp[0][0]=arr[0]# 默认res初始为1
    for j in range(1,n):
        dp[0][j]=dp[0][j-1]+arr[j]
        if dp[0][j]==k:
            res=max(res,j+1)
    # 初始化对角线
    for i in range(1,n):
        dp[i][i]=arr[i]

    # 递推
    for i in range(1,n):
        for j in range(i+1,n):
            dp[i][j]=dp[i][j-1]+arr[j]
            if dp[i][j]==k:
                res=max(res,j-i+1)

    return res

# if __name__ == "__main__":
#     while True:
#         try:
#             N,k=map(int,input().split(' '))
#             arr=list(map(int,input().split(' ')))
#             res=run(arr,k)
#             print(res)
#         except:
#             break

# 方法2：前缀和，同样超出内存限制
def run2(arr,k):
    n=len(arr)
    if n==1:
        return 1 if arr[0]==k else -1

    pre_sum=[0]# 额外的辅助0
    for i in range(0,n):
        pre_sum.append(pre_sum[-1]+arr[i])
    # print(pre_sum)

    res=-1
    for i in range(1,n+1):
        for j in range(i,n+1):
            if pre_sum[j]-pre_sum[i-1]==k:
                res=max(res,j-i+1)

    return res


# if __name__ == "__main__":
#     while True:
#         try:
#             N,k=map(int,input().split(' '))
#             arr=list(map(int,input().split(' ')))
#             res=run2(arr,k)
#             print(res)
#         except:
#             break

# 方法3：前缀和+哈希表
def run3(arr,k):
    n=len(arr)
    rec=dict()# 存储每一个前缀和对应的下标
    rec[0]=-1# 理由见下方

    res=-1

    pre_sum=0
    for i in range(n):
        pre_sum+=arr[i]
        if pre_sum-k in rec:
            res=max(res, i-rec[pre_sum-k])# pre_sum-k可能为0，此时即使arr中没有0，也应该满足pre_sum-k in rec。
            # 所以要额外给rec添加一个key为0值为-1的键值对（值为-1没有实际意义，只是为了能够和后面的逻辑统一）
        if pre_sum not in rec:
            rec[pre_sum]=i

    return res
if __name__ == "__main__":
    while True:
        try:
            N,k=map(int,input().split(' '))
            arr=list(map(int,input().split(' ')))
            res=run3(arr,k)
            print(res)
        except:
            break