好资源导航 » 文章资讯 » 用C++编写一个程序，找出和为零的最大子数组的长度

用C++编写一个程序，找出和为零的最大子数组的长度

2023-06-21 10:17:03 87

假设我们给出了一个由N个整数组成的数组，其任务是找到具有最大长度的子数组的长度。如果不存在任何长度为最大值或总和等于0的子数组，则返回'0'。例如，

输入1-

N = 8
A[ ] = {15, -5, -1, 5,1, 4 }

输出-

说明-具有零和的最大子数组是{-5,-1,5,1}，其长度为4。

输入2-

N = 5
A[ ] = {3, 2 ,4, 8, -1}

输出-

说明-由于不存在总和为零的子数组，因此输出为“0”。

解决这个问题的方法

有几种方法可以解决这个特定问题。在线性时间内求解最合适的算法O(n)是使用哈希表。

这个想法是创建一个哈希表来存储所有子数组的总和，这些子数组的总和存储为键，索引存储为值。

我们将首先遍历整个数组并存储当前的总和。我们将检查当前总和是否在哈希表中可用。如果它存在于哈希表中，则更新子数组的最大长度。

输入N大小的数组。

函数lenMax(int*arr,intsize)将数组及其大小作为输入，返回包含和为零的子数组的最大长度。

包含键作为总和和值作为索引的无序整数映射检查是否有任何和是否重复。

迭代数组元素并找到数组的当前总和，如果总和存在于哈希表中，然后找到子数组的最大长度。如果没有，则将新的总和及其索引插入到哈希表中。

返回最大长度作为输出。

示例

#include
using namespace std;
int lenMax(int *arr, int size){
   unordered_mapmp;
   int sum=0;
   int maxlen=0;
   for(int i=0;i输出结果
如果我们运行上面的代码，它会将输出打印为，
5
sum=0的最大子数组是{-2,2,-8,1,7}。因此，最大子数组的长度为“5”。

返回顶部
514930285
czq8825@qq.com

用C++编写一个程序，找出和为零的最大子数组的长度

解决这个问题的方法

示例

热门推荐

随机推荐