Mündəricat
Problem bəyanat
Bitişik Array LeetCode Həlli – İkili massiv verilmişdir nums, qayıt bərabər sayda bitişik alt massivin maksimum uzunluğu 0 və 1.
Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Izahat
İndi biz nə edəcəyik, bütün çevirmək “0”-dan “-1”ə qədər nümunədə belə bir şey əldə edirik:- [1, -1, -1, 1, -1, 1, 1]. Əgər bunu görürsünüzsə, problem bir qədər cəmi olan ən uzun alt massiv uzunluğunu qaytarmağa bənzəyir “SIFIR”
Çünki bərabər sayı. 1 və 0-dan ibarət olduğuna görə biz 0-ı -1 ilə əvəz etdik. Deməli, bu o deməkdir ki, eyni ilə bərabər yox olacaq. 1 və -1.
Bu, hər hansı bir alt massivdə bərabər bir nömrə varsa, budur. 1 & -1-in cəmi 0 olacaq. Cəmi 0 olan o submassiv uzunluğunu qaytarmalıyıq. Və ən uzun submassiv tapmalıyıq.
Bu problemi istifadə edərək necə həll edəcəyimizi görək HashMap.
Biz məcmu məbləğin köməyindən istifadə edəcəyik, yəni 0-cı indeksdən 6-cı indeksə qədər olan məbləğ nə deməkdir.
Bu məcmu məbləğdən istifadə edərək, bu problemi O(N) şəklində həll edəcəyik.
Bizim hashMap, açarımız və dəyərimiz olacaq.
- Əvvəlcə qazancımızın 0 olduğunu və -1 indeksində olduğumuzu fərz edək
- Biz irəliyə doğru hərəkət edirik və 1 qazanc əldə edirik. Və istinad üçün hasshmapımızda biz qoyuruq açar 0 -> -1 dəyər. Niyə belədir, çünki əvvəlcə biz heç yerdəyik və qazancımız 0 və son cavabımızdır -0 indeksində 1-dır.
Just hold on you will understand - 0 indeksində biz 1 alırıq. Əgər HashMap-a baxsaq, 1 üçün açar-dəyər cütümüz varmı? Xeyr, o zaman yaradacağıq açar 1 -> 0 dəyəri hasshmap-da cütləşdirin.
Our cumulative sum is 0 + 1 = 1 - İndi indeks 1-ə keçməklə biz -1 qazanc və 1 itki alırıq. İndi qazancımız 0 olur, çünki
Our cumulative sum is 1 + (-1) = 0Beləliklə, onun təmsil etdiyi şey -1-ci indeksdən 1-ci indeksə olan Səyahətdədir, biz alt massiv tapdıq, yəni [1, 0]. Alt massiv bərabər nömrəyə malikdir. 0s & 1s. İndi onun uzunluğunu hesablamaq üçün indeks -1-dən indeks 1-ə qədər səyahətə başladıq.Thus, 1 - (-1) = 2. - Beləliklə, bunu izləmək üçün 2 başlanğıcımızı qoyuruq açar 0 və dəyəri -1. İndi ümid edirəm ki, bir az da fikrin var. Biz onu yeniləyəcəyik
current & final-ans with 2 - İndi daha da irəliləyərək və indeks 2-də -1 kimi qazanc əldə etdik
Our cumulative sum is 0 + (-1) = -1Hashmap -1-ə baxsaq, biz bunu edəcəyik açar-dəyər cütü -1 -> 2. - İndi daha da irəliləyərək və indeks 3-də biz 1 alırıq və qazancımız 0 olur
Our cumulative sum is 1 + (-1) = 0. Hashmap-ə baxsaq, 0 -1 dəyəri ilə mövcuddur. İndi onun uzunluğunu hesablamaq üçün indeks 2-dən indeks 3-ə qədər səyahətə başladıq.Thus, 3 - (-1) = 4, sonra bizim yeniləyincurrent & final-ans with 4Və indiyə qədər biz tapdıq 4 ölçülü alt massiv - İndi daha da irəliləyərək və indeks 4-də -1 kimi qazanc əldə etdik
Our cumulative sum is 0 + (-1) = -1. Hashmap-a baxsaq -1-də mövcuddur açar-dəyər cütü -1 -> 2. Səyahətdə 3-cü indeksdən 4-cü indeksə daha bir alt massiv əldə etdik. Ancaq uzunluğunu hesablasaq, olacaq4 - (+2) = 2& yeniləyin 2 ilə cərəyan və müqayisə edin final - yəni 4 azdır, biz bunu nəzərə almayacağıq. - İndi daha da irəliləyərək və indeks 5-də biz 1 alırıq və qazancımız 0 olur
Our cumulative sum is 1 + (-1) = 0. Səyahətdə 4-cü indeksdən 5-ci indeksə daha bir alt massiv əldə etdik. uzunluğunu hesabla, o olacaq5 - (-1) = 6, sonra bizim yeniləyincurrent & final-ans with 6. - Nəhayət, 6-cı indeksdə hərəkət edərək, 1 alırıq və qazancımız 1 kimi olur
Our cumulative sum is 0 + 1 = 1. Hashmap-a baxsaq, 1-də mövcuddur açar-dəyər cütü 1 -> 0. Səyahətdə 5-ci indeksdən 6-cı indeksə daha bir alt massiv əldə etdik. Uzunluğunu hesablasaq, o olacaq6 - (0) = 6& ilə müqayisə edin cari və yekun - yəni 6 ki, ona bərabərdir. - Sonda bərabər nömrəyə malik 2 böyük alt massiv alırıq. 1s və 0s
- [1,0,0,1,0,1]
- [0,0,1,0,1,1]
Kodu
Bitişik alt sətir üçün Java kodu
class Solution {
public int findMaxLength(int[] nums) {
if (nums == null || nums.length == 0) { // Base Case
return 0;
}
// Converting all 0 to -1
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0) nums[i] = -1;
}
int sum = 0; // current
int max = 0; // final-ans
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // put reference in the starting of 0 & -1, as i have tell you in the starting
for(int i = 0; i < nums.length; i++){
sum += nums[i]; // cumulative sum
if(map.containsKey(sum)){ // if cumulative sum key :- 0, -1, 1 already present
int last = map.get(sum); // we get it's value
max = Math.max(max, i - last); // and update max
}
else{ // if it's not present then create it's key-value pair
map.put(sum, i);
}
}
return max; // finally return it
}
}
Bitişik altsətir üçün C++ kodu
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int,int> mp; //map of <gain,index> form
mp[0]=-1; //add starting index with default gain of 0 at -1
//change all zeros to -1
for(int i=0;i<nums.size();i++){
nums[i]==0?nums[i]=-1:nums[i]=1;
}
int sum=0,res=0;
for(int i=0;i<nums.size();i++){
//cumulative sum
sum+=nums[i];
//check if value already exists in the map
if(mp.find(sum)!=mp.end()){
//finding the length of possible subarray and comparing with the max result
res=max(res,i-mp[sum]);
}
else{
//adding value to our map
mp[sum]=i;
}
}
return res;
}
};
Bitişik Alt Dizi üçün Python Kodu
class Solution(object):
def findMaxLength(self, nums):
count = 0
max_length=0
table = {0: 0}
for index, num in enumerate(nums, 1):
if num == 0:
count -= 1
else:
count += 1
if count in table:
max_length = max(max_length, index - table[count])
else:
table[count] = index
return max_length
Bitişik Array LeetCode Həlli üçün Mürəkkəblik Təhlili
Zamanın mürəkkəbliyi
O (N)
Kosmik Mürəkkəblik
O (N)
