1
Problème de sous-réseau: Compte tenu du tableau d'entiers A (seulement des nombres positifs), existe-t-il un sous-réseau continu de longueur quelconque avec la somme S? La solution de fenêtre coulissante à ceci est O (N).Nombreuses requêtes de sous-réseaux
Maintenant, si nous avons beaucoup de telles requêtes S sur un tableau statique, nous pouvons faire un pré-traitement. Nous pouvons calculer toutes les sommes de sous-tableaux en O (N^2) et les stocker dans une table de hachage. Cela prend également l'espace O (N^2). Ensuite, nous pouvons traiter les requêtes dans O (1) en recherchant simplement S à partir de la table de hachage
Ma question est, y a-t-il un pré-traitement O (N log N)? Même si cela signifie déposer les requêtes à O (log N).
Qu'est-ce qu'une solution de fenêtre coulissante à cette approche O (N) '? Avez-vous complètement spécifié le problème? – MBo
Comprenez-vous parfaitement le problème de base de la somme des sous-réseaux qui est bien connu? –
Cela semble un peu difficile à choisir un sous-tableau, vous devrez choisir deux indices et qui équivaut à O (N ** 2) –