Come eseguire iterazioni su un array di numeri interi per trovare una sequenza basata su una soluzione O (N)?

Question

Ho visto la seguente domanda e ho cercato di trovare una risposta.

Question: Given a sequence of positive integers A and an integer T, return whether there is a *continuous sequence* of A that sums up to exactly T 
Example 
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7 

Note: We are looking for an O(N) solution. There is an obvious O(N^2) solution which is a good starting point but is not the final solution we are looking for. 

La mia risposta alla domanda di cui sopra è:

public class Tester { 
    public static void main(String[] args) { 
     int[] myArray = {23, 5, 4, 7, 2, 11}; 
     System.out.println(isValid(myArray, 20)); 
    } 

    public static boolean isValid(int[] array, int sum) { 
     int pointer = 0; 
     int temp = 0; 

     while (pointer < array.length) 
     { 
      for (int i = pointer; i < array.length; i++) 
      { 
       if (array[i] > sum) 
        break; 

       temp += array[i]; 
       if (temp == sum) 
        return true; 
       else if (temp > sum) 
        break; 
       // otherwise continue 
      } 

      temp = 0; 
      pointer++; 
     } 

     return false; 
    } 
} 

penso che la mia risposta è O (N^2), che non è accettabile sulla base di una domanda. Hai idea di cosa sia la soluzione basata su O (N)? Grazie

Answer 1

Hai solo bisogno di anello di una volta in realtà che è O (N)

iniziare ad aggiungere dall'indice 0 e una volta superato lo sum inizia a rimuovere da th e inizio della matrice. se temp scende al di sotto di sum continua in loop.

public static boolean isValid(int[] array, int sum) { 
    int init = 0,temp = 0; 

    for (int i = 0; i < array.length; i++) { 
     temp += array[i]; 
     while (temp > sum) { 
     temp -= array[init]; 
     init++; 
     } 
     if (temp == sum) 
     return true; 
    } 
    return false; 
    } 

Answer 2

Quello che dovresti fare è avere due indici (start e stop) quindi aumentare stop finché la somma non è richiesta (e restituire true) o superiore. Quindi aumenti start finché la somma non è richiesta (e restituisci true o inferiore. Quindi lo ripeti finché non raggiungi la fine dell'array. Puoi aggiornare la somma in modo incrementale (aggiungi l'elemento quando aumenti stop e sottrai quando aumenti start .) Questo dovrebbe essere O (N)

Ecco un esempio:..

public class t { 
    public static void main(String[] args) { 
     int[] myArray = {23, 5, 4, 7, 2, 11}; 
     System.out.println(isValid(myArray, 20)); 
    } 

    public static boolean isValid(int[] array, int sum) { 
     int start = 0; 
     int stop = 0; 
     int tsum = 0; 

     while(true) 
     { 
      if(tsum < sum) 
      { 
       if(stop >= array.length) 
        break; 
       tsum += array[stop]; 
       stop++; 
      } 
      else if(tsum > sum) 
      { 
       tsum -= array[start]; 
       start++; 
      } 
      else if(tsum == sum) 
       return true; 

      // System.out.println(start + " -- " + stop + " => " + tsum); 
     } 

     return false; 
    } 
}