資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究用 C++ 列印子陣列，其中子陣列和為 0
在本題中，我們會得到一個整數值陣列，我們必須打印出該陣列中所有和為 0 的子陣列。
我們舉個例子，以便更好地理解該主題，
Input: array = [-5, 0, 2, 3, -3, 4, -1] Output: Subarray with sum 0 is from 1 to 4. Subarray with sum 0 is from 5 to 7 Subarray with sum 0 is from 0 to 7
為了解決此問題，我們將檢查所有可能的子陣列。檢查這些子陣列的和是否等於 0，若等於 0，則打印出來。此解決方案易於理解，但複雜度較高，時間複雜度為O(n^2)。
解決此問題的更佳方案是使用雜湊。為了解決此問題，如果和等於 0，我們將找到它並將其新增到雜湊表中。
演算法
Step 1: Create a sum variable. Step 2: If sum =0, subarray starts from index 0 to end index of the array. Step 3: If the current sum is in the hash table. Step 4: If the sum exists, then subarray from i+1 to n must be zero. Step 5: Else insert into the hash table.
示例
#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){
unordered_map<int, vector<int> >map;
vector <pair<int, int>> out;
int sum = 0;
for (int i = 0; i < n; i++){
sum += arr[i];
if (sum == 0)
out.push_back(make_pair(0, i));
if (map.find(sum) != map.end()){
vector<int> vc = map[sum];
for (auto it = vc.begin(); it != vc.end(); it++)
out.push_back(make_pair(*it + 1, i));
}
map[sum].push_back(i);
}
return out;
}
int main(){
int arr[] = {-5, 0, 2, 3, -3, 4, -1};
int n = sizeof(arr)/sizeof(arr[0]);
vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n);
if (out.size() == 0)
cout << "No subarray exists";
else
for (auto it = out.begin(); it != out.end(); it++)
cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl;
return 0;
}輸出
Subarray with sum 0 is from 1 to 1 Subarray with sum 0 is from 0 to 3 Subarray with sum 0 is from 3 to 4 Subarray with sum 0 is from 0 to 6 Subarray with sum 0 is from 4 to 6
更新日期：2020-01-17
218 次瀏覽
廣告