somma Subsequence

Question

dato un array di interi es [1, 2, -3, 1] trovare se v'è un sotto-sequenza che somma a 0 e restituirlo (es [1, 2, -3] o [2, -3, 1]).
Controllare ogni sottodivisione è O(n^2) che è troppo inefficiente. Qualche idea per miglioramenti?

Answer 1

Crea un nuovo array con ogni elemento uguale alla somma degli elementi precedenti più quello.

ingresso:

1 4 -3 -4 6 -7 8 -5 

diventa:

1 5 2 -2 4 -3 5 0 
^   ^

poi cercare gli elementi che corrispondono nella matrice risultante.

Poiché questi rappresentano posizioni in cui il cambiamento complessivo della funzione è zero, si scoprirà che se la loro posizione è i e k, allora la sottosequenza (i + 1, k) è una sottosuccessione a somma zero. (In questo caso, [2: 6]).

Inoltre, eventuali zeri nella tabella indicano che la sottosequenza (0, k) è una sottosuccessione a somma zero. Per la ricerca, una tabella hash o un altro localizzatore di collisione veloce rende questo O (N) da eseguire.

Answer 2

fare una somma parziale, memorizzare i valori somma in una tabella hash con indice di campo

Se mai un valore di somma che hai già visto, ritornare 1 + l'indice nella tabella hash, e la corrente indice. Questa soluzione è O (n) tempo complessità.

Non c'è bisogno di un nuovo array. La complessità dello spazio è O (N) a causa dell'hash. attuazione

---

un pitone:

input = [1, 4, -3, -4, 6, -7, 8, -5] 
map = {} 
sum = 0 
for i in range(len(input)): 
    sum += input[i] 
    if sum in map: 
     print map[sum][0] + 1, "to", i 
    map[sum] = (i, sum) 

noti che ripetute sottosequenze non sono mostrate, ad esempio: Se (da 1 a 2) è una sottosequenza e (3 a 4), (da 1 a 4) non verrà mostrato. È possibile ottenere questo comportamento memorizzando liste in ogni posizione della mappa:

for x in map[sum]: 
    print x[0]+1, "to", i 
map[sum].append((i, sum)) 

Answer 3

A C++ implementazione con logica simile alla risposta di Fabricio.

pair<int, int> FindSubsequenceSum(const vector<int>& arr)  
{ 
    map<int, int> sumMap; 
    map<int, int>::iterator it; 
    int sum = 0; 
    for (int i = 0; i < arr.size(); i++) 
    { 
    sum += arr[i]; 
    it = sumMap.find(sum); 
    if (it != sumMap.end()) 
    { 
     return make_pair(it->second + 1, i); 
    } else { 
     sumMap.insert(make_pair(sum, i)); 
    } 
} 

int main() 
{ 
    int arr[] = {1,4,-3,-4,6,-7,8,-5}; 
    vector<int> input(arr, arr + sizeof(arr)/sizeof(arr[0])); 
    pair<int, int> result = FindSubsequenceSum(input); 

    cout << "(" << result.first << "," << result.second << ")" << endl; 

    return 0; 
} 

Output: 
(2,6) 

Answer 4

Di seguito si riporta l'implementazione Java della soluzione suggerita da @Fabricio

public static int countAllSubSequenceForZeroSum(int[] array) { 
    int count = 0; 
    Map<Integer, Integer> encounteredSum = new HashMap<>(); 
    int prev = array[0]; 
    if(prev == 0) { 
     count++; 
     System.out.println("Found at index: "+0); 
    } 
    for (int i = 1; i < array.length; i++) { 
     prev += array[i]; 
     if(encounteredSum.containsKey(prev)) { 
      System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev)); 
      printSequenceForZeroSum(array, i); 
      count++; 
     } else { 
      encounteredSum.put(prev, i); 
     } 
    } 
    return count; 
} 

public static void printSequenceForZeroSum(int[] array, int endIndex) { 
    int sum = array[endIndex]; 
    while(sum!=0) { 
     System.out.print(array[endIndex]+ " "); 
     sum += array[--endIndex]; 
    } 
    System.out.println(array[endIndex]); 
}