資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告