Nombre de sous-séquences contiguës résumées à une cible donnée

Question

Je ne pouvais pas trouver une manière efficace (mieux que $ O (n ^ 2) $) pour compter le nombre de sous-séquences contiguës d'un tableau d'entiers positifs et négatifs résumant à un nombre donné $ k $.

Par exemple, si $ A = {2,5,6, -1 } $ et $ k = 5 $ Ensuite, la réponse est $2$, puisque les deux $5$ et $6,-1$ résumer $5$.