给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ，求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。
[1,2,3]的连续子数组有[1,2]，[2,3]，[1,2,3] ，但是[1,3]不是
数据范围： 
，
，
要求：空间复杂度)
， 时间复杂度
要求：空间复杂度
[编程题]和为K的连续子数组
参考：https://blog.csdn.net/weixin_43982698/article/details/107135036解法：哈希假设s(i)是子数组arr[0…i]的累加和,那么s(j)就代表arr[0…j]的累加和，那么可求得arr[j+1…i]=s(i)-s(j)。流程： 1.初
展开全文
解法一：暴力解法 此题需要求解连续子数组元素的和等于目标值的最长子数组长度，因此需要两个变量分别确定子数组的头和尾。 暴力解法的思路如下：定义两个变量i、j，分别表示当前子数组的头尾。其中，i指针从第0个位置开始遍历，用来表示子数组的头；j指针从i开始遍历，表示子数组的尾。在遍历过程中，若求得当前子
展开全文
未排序数组中累加和为给定值的最长子数组长度 为了解答题目，引入一个概念，s(i)代表子数组arr[0..i]所有元素的累加和。那么子数组arrj-1, i的累加和为s(i)-s(j-1)。 设置变量sum=0，表示从0位置开始一直加到i位置所有元素的和。设置变量len＝0，表示累加和为k的最长子数
展开全文
【模拟】
题目要求时间复杂度为O(n)，说明最多只能有一个for循环
空间复杂度为O(n)，说明需要一个和arr长度一样的数组或字典
定义数组ans，用来存放满足要求的子数组的长度
字典用来存放前i个元素和及其索引
当sum_[j]-sum_[i]==k的时候说明出现了和为k的子数组，此时只需要变
展开全文
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* max length of the subarray sum = k
* @param arr int整
展开全文
描述 给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有连续子数组中累加和为k的最长子数组长度。保证至少存在一个合法的子数组。 方法一 思路 枚举法，暴力查找； 所谓的连续子数组是指对于一个数组arr，从下标i到下标j的一段数据构成的新数组，而为了找出连续子数组中
展开全文
为了解答题目，引入一个概念，s(i)代表子数组arr[0..i]所有元素的累加和。那么子数组arrj-1, i的累加和为s(i)-s(j-1)。
设置变量sum=0，表示从0位置开始一直加到i位置所有元素的和。设置变量len＝0，表示累加和为k的最长子数组长度。定义一个HashMap，其中key
展开全文
思路如下：
1.最关键的点在于累计和列表，这个累计和列表在后续中可以隐去，但是解决问题的关键在于考虑累计和列表
累计和列表即求到当前id下数组的和 s[i] = a[0]+a[1]+...a[i-1]
2.那么任意的一个子数组都可以由累计和列表推出 s[j]-s[i]
想要满足子数组的和等于k 即满
展开全文
连续子数组和的问题 -> 前缀和
import java.util.*;
public class Solution {
public int maxlenEqualK (int[] arr, int k) {
// prefixSumMap: 前缀和 -> 前缀和为su
展开全文
问题信息
难度：
40条回答
367收藏
5599浏览
通过挑战的用户
查看代码-
2022-12-28 16:34:42
-
2022-10-12 16:01:44
-
2022-09-27 11:22:40
-
2022-09-16 15:28:23
-
2022-09-16 10:53:59
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
