Mảng liền kề trong C ++

Giả sử chúng ta có một mảng nhị phân, chúng ta phải tìm độ dài lớn nhất của một mảng con liền kề với số lượng bằng nhau là 0 và 1. Vì vậy, nếu đầu vào là [0,1,0], thì đầu ra sẽ là 2 là [0, 1] hoặc [1,0] là mảng liền kề lớn nhất với số lượng 0 và 1 bằng nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, n:=kích thước của nums, sum:=0
• tạo bản đồ m, đặt m [0]:=- 1
• cho tôi trong phạm vi từ 0 đến kích thước của nums - 1
  • sum:=sum + 1 khi nums [i] là 1, ngược lại sum:=sum - 1
  • nếu tổng bằng m thì ret:=max của ret và i - m [sum], nếu không thì m [sum]:=i
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
   }
};
main(){
   vector<int> v = {0,1,0,0,1};
   Solution ob;
   cout << (ob.findMaxLength(v));
}

Đầu vào

[0,1,0,0,1]

Đầu ra

4