首页 > 试题广场 >

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

[编程题]未排序数组中累加和为给定值的最长子数组长度
  • 热度指数：6605 时间限制：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

输出

3

备注:

算法知识视频讲解
开通博客
头像 红玉圆
发表于 2020-05-10 14:19:22
题目描述给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度输入描述:第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出第二行N个整数表示数组内的数输出描述:输出一个整数表示答案示例1输入5 01 -2 1 1 1输出3思 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 哈哈～柳暗花明
发表于 2020-07-28 20:32:27
m存储前i项和对应下标，a存储前i项和，ans最大长，即求第i项时m[a-k]是否存在 def solve(l, n, k): m = {0:-1} a = ans = 0 for i in range(n): a += l[i] if a n 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 瓜瓜请多指教
发表于 2020-07-18 11:45:03
include <bits/stdc++.h> using namespace std; int main(){ int n,k,t,len=0; cin>>n>>k; vector<int> arr(n+1,0); for(i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 吴清忠201808271120204
发表于 2024-04-13 21:59:58
#include <iostream> #include <unordered_map> #include <vector> using namespace std; int main() { int n; int target; st 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客695415901号
发表于 2024-04-11 00:22:31
抄的，自己写的前缀和+hash没有处理好0值并且写的很臭，下面的代码相对美观 import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static int maxLength 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Allen2023wp
发表于 2023-06-15 10:22:14
N,k = map(int,input().split()) arr = list(map(int,input().split())) sum = 0 length = 0 tmp_dict = {0:-1} for i in range(len(arr)): sum += arr[i] 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 快支棱起来的椰子很愤怒
发表于 2022-01-07 17:18:23
n, k = map(int, input().split()) l = list(map(int, input().split())) tree = {0: -1} su = 0 res = 0 for i in range(len(l)): su += l[i] if su in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客318213606号
发表于 2022-08-04 22:02:02
方法1：动态规划开二维数组超出内存限制了。。。 方法2：前缀和，同样超出内存限制了。。。 方法3：前缀和+哈希表，终于通过了 # 方法1，基于二维数组的dp，提交后只通过一个测试用例，原因是超出内存限制，测试用例中的数组arr太大了。。。 def run(arr,k): n=len(arr) 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

队列
上传者：小小
难度：
21条回答 5391浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号