สมมติว่าเรามีอาร์เรย์ไบนารี เราต้องหาความยาวสูงสุดของอาร์เรย์ย่อยที่อยู่ติดกันด้วยจำนวนเท่ากับ 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
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
[0,1,0,0,1]
ผลลัพธ์
4
