数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学编写一个 C++ 程序来查找和为零的最大子数组的长度。
假设我们给定一个包含 N 个整数的数组，任务是找到长度最大的子数组。如果没有任何子数组的长度最大或和等于 0，则返回 '0'。例如：
输入-1 −
N = 8
A[ ] = {15, -5, -1, 5,1, 4 }输出 −
4
说明 − 和为零的最大子数组是 {-5, -1, 5, 1}，长度为 4。
输入-2 −
N = 5
A[ ] = {3, 2 ,4, 8, -1}输出 −
0
说明 − 由于不存在和等于零的子数组，因此输出为 '0'。
解决此问题的方法
有几种方法可以解决这个问题。最合适的算法是使用哈希表，可以在线性时间 O(n) 内解决。
其思想是创建一个哈希表，存储所有子数组的和，其中和作为键，索引作为值。
我们将首先遍历整个数组并存储当前和。我们将检查哈希表中是否存在当前和。如果存在于哈希表中，则更新子数组的最大长度。
输入数组大小 N。
函数 `lenMax(int *arr, int size)` 接收一个数组及其大小作为输入，返回包含和为零的最大子数组的长度。
一个无序整数映射，其中键为和，值为索引，用于检查是否有任何和重复。
迭代数组元素并找到数组的当前和，如果和存在于哈希表中，则找到子数组的最大长度。如果没有，则将新和及其索引插入哈希表。
返回最大长度作为输出。
示例
#include<bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size){
unordered_map<int,int>mp;
int sum=0;
int maxlen=0;
for(int i=0;i<size;i++){
sum+=arr[i];
if(arr[i]==0 && maxlen==0){
maxlen=1;
}
if(sum==0){
maxlen=i+1;
}
if(mp.find(sum)!= mp.end()){
maxlen= max(maxlen, i-mp[sum]);
} else {
mp[sum]=i;
}
}
return maxlen;
}
int main(){
int N=6;
int A[N]={15,-2,2,-8,1,7,10,23};
cout<<lenMax(A,N)<<endl;
return 0;
}输出
如果运行以上代码，它将输出：
5
和为 0 的最大子数组是 {-2, 2, -8, 1, 7}。因此，最大子数组的长度为 '5'。
更新于：2021年2月5日
250 次浏览
广告