Somme subséquente

Question

Étant donné un tableau d'entiers eg [1, 2, -3, 1] trouver s'il existe une sous-séquence dont la somme est égale à 0 et le retourner (par exemple [1, 2, -3] o [2, -3, 1] ).
La vérification de chaque sous-séquence est O(n^2) ce qui est trop inefficace. Une idée d'amélioration ?

Answer 1

Créez un nouveau tableau dont chaque élément est égal à la somme des éléments précédents plus celui-là.

Entrée :

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

Devient :

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

Ensuite, recherchez les éléments qui correspondent dans le tableau résultant.

Puisque ceux-ci représentent des emplacements où la variation globale de la fonction est nulle, vous constaterez que si leur position est i et k, alors la sous-séquence (i+1, k) est une sous-séquence à somme nulle. (Dans ce cas, [2:6]).

De plus, tout zéro dans la table indique que la sous-séquence (0, k) est une sous-séquence à somme nulle. Pour la recherche, une table de hachage ou un autre localisateur de collision rapide permet d'effectuer cette opération en O(N).

Answer 2

Faire une somme courante, en stockant les valeurs de la somme dans une table de hachage avec l'index du tableau.

Si vous obtenez une valeur de somme que vous avez déjà vue, renvoyez 1+l'indice dans la table de hachage, et l'indice actuel. Cette solution est Temps O(n) complexité.

Pas besoin d'un nouveau tableau. La complexité spatiale est O(N) à cause du hachage.

---

Une implémentation 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)

Notez que les sous-séquences répétées ne sont pas représentées, exemple : Si (1 à 2) est une sous-séquence et (3 à 4), (1 à 4) ne sera pas affiché. Vous pouvez obtenir ce comportement en stockant des listes dans chaque position de la carte :

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

Answer 3

Voici l'implémentation en java de la solution suggérée par @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 4

Une implémentation C++ avec une logique similaire à la réponse 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)

Answer 5

Une implémentation en scala :

List(1,2,3,4).scan(0){_+_}

le résultat sera Liste(0, 1, 3, 6, 10) .

ou vous le pouvez :

List(1,2,3,4).scan(0){_+_}.tail  

obtenir Liste(1, 3, 6, 10)