525. Contiguous Array

using System.Collections.Generic;
public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> countMap = new Dictionary<int, int> { {0, -1} };
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.ContainsKey(count)) {
                maxLength = Math.Max(maxLength, i - countMap[count]);
            } else {
                countMap[count] = i;
            }
        }
        
        return maxLength;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindMaxLength(vector<int>& nums) {
        unordered_map<int, int> countMap = new unordered_map<int, int> { {0, -1} };
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.count(count)) {
                maxLength = max(maxLength, i - countMap[count]);
            } else {
                countMap[count] = i;
            }
        }
        
        return maxLength;
    }
}

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        countMap.put(0, -1);
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.length; i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.containsKey(count)) {
                maxLength = Math.max(maxLength, i - countMap.get(count));
            } else {
                countMap.put(count, i);
            }
        }
        
        return maxLength;
    }
}

var findMaxLength = function(nums) {
    let countMap = new Map();
    countMap.set(0, -1);
    let maxLength = 0;
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        count += (nums[i] === 1 ? 1 : -1);
        
        if (countMap.has(count)) {
            maxLength = Math.max(maxLength, i - countMap.get(count));
        } else {
            countMap.set(count, i);
        }
    }
    
    return maxLength;
};

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        count_map = {0: -1}
        max_length = 0
        count = 0
        
        for i, num in enumerate(nums):
            count += 1 if num == 1 else -1
            
            if count in count_map:
                max_length = max(max_length, i - count_map[count])
            else:
                count_map[count] = i
        
        return max_length

func findMaxLength(nums []int) int {
    countMap := map[int]int{0: -1}
    count, maxLength := 0, 0
    
    for i, num := range nums {
        if num == 1 {
            count++
        } else {
            count--
        }
        
        if prevIndex, exists := countMap[count]; exists {
            maxLength = max(maxLength, i - prevIndex)
        } else {
            countMap[count] = i
        }
    }
    
    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подarrayа. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.

Итеративно пройдите по arrayу nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подarrayа между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подarray длиннее.

Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации return max_length.

😎