मान लीजिए हमारे पास एक बाइनरी सरणी है, हमें समान संख्या में 0 और 1 वाले सन्निकट उपसरणी की अधिकतम लंबाई ढूंढनी है। इसलिए यदि इनपुट [0,1,0] है, तो आउटपुट 2 होगा क्योंकि [0,1] या [1,0] समान संख्या में 0 और 1 वाली सबसे बड़ी सन्निकट सरणी है।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
ret := 0, n := nums का आकार, sum := 0- एक मैप
mबनाएं,m[0] := -1सेट करें i = 0 से nums का आकार - 1तक:sum := sum + 1 जब nums[i] 1 है अन्यथा sum := sum - 1- यदि
sum, m में है, तोret := max(ret, i - m[sum]), अन्यथाm[sum] := i
retलौटाएं
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ret = 0;
int n = nums.size();
int sum = 0;
map<int, int> m;
m[0] = -1;
for(int i = 0; i < nums.size(); i++){
sum += nums[i] == 1 ? 1 : -1;
if(m.count(sum)){
ret = max(ret, i - m[sum]);
} else m[sum] = i;
}
return ret;
}
};
int main(){
vector<int> v = {0,1,0,0,1};
Solution ob;
cout << (ob.findMaxLength(v));
}
इनपुट
[0,1,0,0,1]
आउटपुट
4