Trovare il subarray più grande con uguale numero di 0 e 01

Question

Quindi, ho un array contenente solo 0 e 1. Devo scoprire il subarray più grande che contiene lo stesso numero di 0 e di 1. Uno può essere un approccio ingenuo ha complessità come O(n^2) dove prendo ogni elemento nel ciclo esterno e calcolare possibili sottoarray nel ciclo interno e mantenere l'aggiornamento della dimensione massima, se trovato. C'è qualche altro approccio migliore (qualcosa come O (n)) che posso usare? Grazie!

Input: arr[] = {1, 0, 1, 1, 1, 0, 0} 
Output: 1 to 6 (Starting and Ending indexes of output subarray) 

Answer 1

Ecco un algoritmo O (n) -time, O (n) -space. Non sono sicuro che sia ottimale, ma batte il tempo quadratico.

L'idea di base è la seguente. Si supponga di eseguire la scansione dalla sinistra dell'array alla registrazione corretta, ad ogni passo, la differenza tra il numero di 1 e il numero di 0. Se si scrive questi valori fuori ad ogni passo, si otterrà qualcosa di simile:

1, 0, 1, 0, 0, 0, 0 
0, 1, 0, 1, 0, -1, -2, -3 

Se si dispone di un sub-array con lo stesso numero di 0 e 1, quindi la differenza netta di 0 e 1 al l'inizio del subarray sarà uguale al numero netto dopo il subarray. Pertanto, questo problema può essere riformulato cercando di trovare due valori uguali nella matrice ausiliaria che sono uguali e il più distanti possibile.

La buona notizia è che ogni voce nell'array è compresa tra -n e + n, quindi è possibile creare una tabella di elementi 2n + 1 e memorizzare in essa gli indici della prima e dell'ultima volta in cui viene visualizzato ciascun numero. Da lì, è facile trovare la gamma più lunga. Nel complesso, ciò richiede O (n) spazio e tutto può essere popolato e ricercato nel tempo O (n).

Spero che questo aiuti!

Answer 2

Prima converti gli zeri in -1. Quindi stai cercando un subarray massimo di somma zero. Un algoritmo per questo è descritto here

Answer 3

public int equalNumber(int arr[]){ 

    int sum[] = new int[arr.length]; 
    sum[0] = arr[0] == 0? -1 : 1; 
    for(int i=1; i < sum.length; i++){ 
     sum[i] = sum[i-1] + (arr[i] == 0? -1 : 1); 
    } 

    Map<Integer,Integer> pos = new HashMap<Integer,Integer>(); 
    int maxLen = 0; 
    int i = 0; 
    for(int s : sum){ 
     if(s == 0){ 
      maxLen = Math.max(maxLen, i+1); 
     } 
     if(pos.containsKey(s)){ 
      maxLen = Math.max(maxLen, i-pos.get(s)); 
     }else{ 
      pos.put(s, i); 
     } 
     i++; 
    } 
    return maxLen; 
}