Wenn die Arrays Ganzzahlen begrenzter Größe enthalten (d. h. im Bereich -u bis u), können Sie dies in O(n+ulogu) time lösen, indem Sie die schnelle Fourier-Transformation verwenden, um die Histogramme jeder Sammlung zusammenzufalten.
Zum Beispiel würde die Menge a=[-1,2,2,2,2,3] durch ein Histogramm mit Werten repräsentiert:
Nachdem alle Histogramme zusammen mit der FFT gefaltet wurden, enthält das resultierende Histogramm Einträge, wobei der Wert für jedes Bin Ihnen die Anzahl der Möglichkeiten zum Kombinieren der Zahlen angibt, um jede mögliche Summe zu erhalten. Um die Antwort auf Ihre Frage mit insgesamt 0 zu finden, müssen Sie nur den Wert des Histogramms für Fach 0 lesen.