Jak iterować po tablicy liczb całkowitych, aby znaleźć sekwencję opartą na rozwiązaniu O (N)?

Question

Widziałem następujące pytanie i próbowałem znaleźć na to odpowiedź.

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. 

Moja odpowiedź na powyższe pytanie brzmi:

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; 
    } 
} 

myślę, że moja odpowiedź jest O (n^2), który jest nie do zaakceptowania w oparciu o pytanie. Czy masz pojęcie, jakie jest rozwiązanie oparte na O (N)? Dzięki

Answer 1

trzeba tylko do pętli raz rzeczywistości, która jest O (N)

rozpocząć dodawanie z indeksu 0 i gdy przekroczysz sum zacznij usuwanie z th e początek tablicy. jeśli temp spadnie poniżej sum kontynuuj zapętlanie.

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

Co należy zrobić, to mieć dwa wskaźniki (start i stop), a następnie zwiększyć stop, aż suma jest wymagana (i wrócić true) lub powyżej. Następnie zwiększasz wartość do start, aż suma będzie wymagała (i zwrócisz true lub mniejszą, a następnie powtarzasz ją, aż dojdziesz do końca tablicy. Możesz aktualizować sumę przyrostowo (dodaj element, zwiększając wartość stop i odejmuj, gdy zwiększysz wartość start). to powinno być O (N)

Oto przykład:..

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; 
    } 
}