algorithm - interview - data structures in c pdf

Suma de la subsecuencia

Question

Dada una matriz de enteros, por ejemplo, [1, 2, -3, 1] encuentre si hay una subsecuencia que suma 0 y devuélvala (por ejemplo, [1, 2, -3] o [2, -3, 1] ).
La comprobación de cada subsecuencia es O(n^2) que es demasiado ineficiente. ¿Alguna idea para mejorar?

Answer 1

A continuación se muestra la implementación java de la solución sugerida por @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]);
}

Answer 2

Haga una suma corriente, almacenando valores de suma en una tabla hash junto con el índice de matriz

Si alguna vez obtiene un valor de suma que ya ha visto, devuelva 1 + el índice en la tabla hash y el índice actual. Esta solución es O (n) complejidad de tiempo .

No hay necesidad de una nueva matriz. La complejidad del espacio es O (N) debido al hash.

Una implementación de Python:

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)

Observe que no se muestran las subsecuencias repetidas, ejemplo: si (1 a 2) es una subsecuencia y (3 a 4), no se mostrará (1 a 4). Puede lograr este comportamiento almacenando listas en cada posición del mapa:

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

Answer 3

Haz una nueva matriz con cada elemento igual a la suma de los elementos anteriores más uno.

Entrada:

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

Se convierte en

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

Luego busque elementos que coincidan en la matriz resultante.

Como estas representan ubicaciones donde el cambio general en la función es cero, encontrará que si su posición es i y k, entonces la subsecuencia (i + 1, k) es una subsecuencia de suma cero. (En este caso, [2: 6]).

Además, los ceros en la tabla indican que la subsecuencia (0, k) es una subsecuencia de suma cero. Para la búsqueda, una tabla hash u otro localizador de colisión rápido hace que este O (N) se realice.

Answer 4

Una implementación en C ++ con lógica similar a la respuesta de 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)