Trovare il primo subarray che sommi a un dato totale

Che mi dici di questo?

• Eseguiamo l'array, calcolando le somme di tutti i prefissi lungo la strada. (O (n) dal momento che possiamo tenere un conto corrente della somma)

• Salviamo le somme che incontriamo in qualche datastructure in cui possiamo cercare per il valore della somma e anche ottenere il prefisso a cui appartiene la somma (vedi sotto per l'implementazione di questo)

• Se la somma del prefisso fino all'indice n è fuori bersaglio di una somma che è la somma di un prefisso precedentemente rilevato, ad esempio, fino all'indice m, allora abbiamo trovato il nostro subarray, l'array da m tonnellata. Poiché sum(prefix(n)) - sum(prefix(m)) = targetSum e subArray(m,n) = prefix(n) - prefix(m) (si spera che questa notazione psuedo sia abbastanza chiara)

Ora il tempo di esecuzione del nostro algoritmo è n * (the time it takes to insert the sum of our prefix to the datastructure + the time it takes to search if we have a certain sum in our datastructure) .

Una scelta ovvia per una struttura dati sarebbe una tabella hashtable con somme come chiavi e il prefisso che sono la somma di valori. Qui la ricerca e l'inserimento prendono O (1) in media, quindi saremo in media O (n), il che sembra piuttosto decente. Il codice potrebbe essere:

public int[] findSubArray(int[] arr, int targetSum){
    Map<Integer, Integer> sumsToIndex = new HashMap<Integer, Integer>();
    int sum = 0;

    for(int index = 0; index <= arr.length; index++){
        if(sumsToIndex.get(sum) == null){
            sumsToIndex.put(sum, index);
        }

        int offTarget = sum - targetSum;
        Integer offTargetPrefix = sumsToIndex.get(offTarget);
        if(offTargetPrefix != null){
            return Arrays.copyOfRange(arr, offTargetPrefix, index);
        }

        if(index < arr.length){
            sum += arr[index];
        }
    }
    return null;
}

Tuttavia, nel caso peggiore, la ricerca in una tabella hash è O (n) se otteniamo un carico di collisioni di navi, non so come questo si estenda qui. Dal momento che le nostre chiavi sono numeri interi, penso che potremmo essere a posto. Ma forse teoricamente siamo ancora nel peggiore dei casi. Rendere fermo il nostro algoritmo O (n ^ 2).

Quello che potremmo fare è utilizzare qualche altra struttura dati, come alberi rosso-neri (con le somme come chiave di ordinamento), dove ricerca e inserimento sono O (log n) nel peggiore dei casi, rendendo il nostro algoritmo O (n log (n)).

Penso di aver trovato una soluzione. Supponi i seguenti numeri e vuoi trovare il primo sottoarray da sommare a 4:

2 -3 7 1 5 -1

Prima di eliminare i numeri negativi, suggerisco di trovare il numero più piccolo (-3) e di aggiungere il suo valore assoluto a tutti i numeri, che richiede O(n) , abbiamo:

5  0  10 4  8 2

Quindi per ogni sub-array con dimensione n, la somma dovrebbe essere n*3 + 4 , se trovi quella somma, allora hai trovato la risposta

Ho scritto il target per i sub-array con dimensione 1, 2, 3 ...

7   10  13  16   19

Ora inizia con 5, è inferiore a 7, puoi continuare, aggiungilo a 0, è minore di 10, e puoi continuare, aggiungerlo a 10, è più di 13, quindi ignorare 5, e per quanto riguarda 0 + 10, è inferiore a 10, in realtà è uguale a 10, significa che hai trovato la risposta, la risposta è -3 + 7 = 4

Cerco di scrivere l'algoritmo verso il basso! ,

 SubArraySumTo(A[], y)
 {
     x = abs(min(A));  // a loop over the array
     foreach (var a in A)
     {
         a+=x;
     }
     int start =0;
     int sum =A[0];
     int i=0;
     while (i < n)
     {
         target = (i - start +1)*x + y;              
         if (sum == target)
         {
              return A[start..i];
         }
         else if (sum < target)
         {
            i++; 
            sum += A[i];
         }
         else if (sum > target)
         {
             start++;
             sum -= A[start];
         }
     }
 }

È un'iterazione con O (2n) nel peggiore dei casi

Se stai cercando una somma s e il totale di tutti gli elementi dell'array è t, allora la somma del primo i e dell'ultimo j elementi deve essere t -s, quindi gli elementi dall'indice i all'indice nj sono esclusivi aggiungere fino a s.

Quindi crei una tabella hash o un albero binario bilanciato per la somma degli ultimi j elementi, iniziando con j = 0, quindi aggiungendo un altro elemento per j = 1, 2, 3, ecc. La tabella hash sarà O (1 ) in media, ma l'albero binario bilanciato è O (log n) nel caso peggiore.

Per ogni j, si controlla se t min s meno la somma dei primi elementi i = n-j è nella tabella hash o albero binario, e procedere fino a j = n e i = 0.

O (n) media usando una tabella hash, ma nessuna garanzia per il caso peggiore. O (n log n) se si utilizza una struttura di ricerca bilanciata.

Come esempio con i dati [1, -3, 4, 8, 2, -14, 3, -1, 10, 6]: Il totale è t = 16, ci è stato dato s = 9, quindi il la somma del primo i e degli ultimi j elementi deve essere 7. L'elenco delle somme degli ultimi j elementi è:

j = 0: 0
j = 1: 0, 6
j = 2: 0, 6, 16
j = 3: 0, 6, 16, 15
j = 4: 0, 6, 16, 15, 18
j = 5: 0, 6, 16, 15, 18, 4
j = 6: 0, 6, 16, 15, 18, 4, 6
j = 7: 0, 6, 16, 15, 18, 4, 6, 14
j = 8: 0, 6, 16, 15, 18, 4, 6, 14, 18
j = 9: 0, 6, 16, 15, 18, 4, 6, 14, 18, 15
j = 10: 0, 6, 16, 15, 18, 4, 6, 14, 18, 15, 16

Quindi calcoliamo la somma dei primi elementi i = 10-j, e 7 meno quella somma deve essere nell'ultima delle somme degli ultimi j elementi.

j =  0, i = 10: 7 -  16 = -9, not found
j =  1, i =  9: 7 -  10 = -3, not found
j =  2, i =  8: 7 -   0 =  7, not found
j =  3, i =  7: 7 -   1 =  6, found
j =  4, i =  6: 7 - (-2) = 9, not found
j =  5, i =  5: 7 -  12 = -5, not found
j =  6, i =  4: 7 -  10 = -3, not found
j =  7, i =  3: 7 -   2 =  5, not found
j =  8, i =  2: 7 - (-2) = 9, not found
j =  9, i =  1: 7 -   1 =  6, found
j = 10, i =  0: 7 -   0 =  7, not found

I primi 1 elementi hanno una somma di 1, gli ultimi 1 o 6 elementi hanno una somma di 6, quindi gli elementi 1..9 o 1..4 hanno una somma di 9. Il tempo è fondamentalmente n inserimenti e ricerche in una struttura di dati.

Le soluzioni pubblicate sopra sembrano buone. Ecco il mio codice per lo stesso. Ci vuole O (n) tempo per completare.

L'output del programma di cui sopra è 2 4. Il che significa che la 2a, 3a e 4a somma di elementi dà il valore di 9. 2nd Element indica l'indice di array di 1 not 2.

class FindArrayProblem {
    public static void main (String[] args) {
        int array[] = {1, -3, 4, 8, 2, -14, 3, -1, 10, 6};
        int sum = 9;
        findSubArray(array,sum);
    }

    static void findSubArray(int[] array, int sum){
        int start = 0 , end =0;
        int tmpSum = array[0] ;
        while (end < array.length) {
            if (tmpSum == sum){
                System.out.println((start + 1) + " " + (end + 1)) ;
                break;
            }
            if (tmpSum <= sum){
               end++ ;
                if (end < array.length)
                    tmpSum += array[end];
            } else {
                tmpSum -= array[start];
                ++ start;
            }
        }
    }
}