Algorithmen und Datenstrukturen

Subarrays mit einer bestimmten Summe

Wenn du ein Array mit Zahlen gegeben hast, möchtest du ermitteln, wie viele Subarrays (Teilarrays) es gibt, deren Summe genau s beträgt.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen – n (die Anzahl der Elemente im Array; 1 ≤ n ≤ 1000) und die Zahl s (). In der nächsten Zeile stehen n ganze Zahlen, jeweils durch ein Leerzeichen getrennt, die die Elemente des Arrays repräsentieren ().

Ausgabe

Das Programm soll eine einzelne ganze Zahl ausgeben – die Anzahl der Subarrays, deren Summe s ist. Falls keine Subarrays existieren, deren Summe s ergibt, soll das Programm 0 ausgeben.

Beispiele

Input
Output
6 33 9 4 20 3 10 5
2
5 -10 10 2 -2 -20 10
3

Erklärung

  1. 9 4 20 3 10 5, 9 4 20 3 10 5
  1. 10 2 -2 -20 10, 10 2 -2 -20 10, 10 2 -2 -20 10
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue