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

[编程题]未排序数组中累加和为给定值的最长子数组长度

热度指数：7076 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度

输入描述:

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

5 0
1 -2 1 1 1

输出

备注:

算法知识视频讲解

Python

Dayanghe

参考大神方法，使用字典方法

循环遍历每个数字，记录累加结果，找到sums-k

while True:
    try:
        n, k = map(int,input().split())
        inputs = list(map(int,input().split()))
        sums = 0
        res = 0
        dict = {0:-1}
        for i in range(n):
            sums+=inputs[i]
            if sums not in  dict:
                dict[sums]=i
            if sums-k in dict:
                res=max(res,i-dict[sums-k])
        print(res)
    except:break

发表于 2019-08-18 17:09:57 回复(0)