Mit einem Array von positiven ganzen Zahlen a und einer ganzen Zahl k versuche ich einen Algorithmus zu finden, der mir die Länge des längsten Subarrays gibt, dessen Summe ist weniger als oder gleich zu k. Ich habe herausgefunden, wie man es in O (n^2) -Zeit löst, versuche aber, mich so nah wie möglich an O (n) zu lösen.Längstes Subarray mit einer Summe kleiner als gleich
Für eine O (n) -Lösung versuche ich einen Startindex und einen Endindex zu erstellen, die mir ein Fenster geben. Ich möchte überprüfen, ob die Summe in diesem Fenster < = k UND ist, wenn die Länge dieses Fensters größer ist als die zuletzt aufgezeichnete Länge. Beim Eintippen bricht jedoch meine Logik zusammen.
Manchmal müssen Sie den Start mehrmals für ein einzelnes "i" verschieben. Versuchen Sie also, Ihren 'else'-Fallkörper in ein 'while (sum> k)' einzufügen. – Gassa
Ich habe nicht sehr genau hingeschaut, aber ein kurzer Blick zeigt, dass Sie "maxLen" nie etwas zuweisen. Ich vermute 'currLen = maxLen' ist rückwärts. Haben Sie versucht, einen Debugger und einen einfachen Testfall zu verwenden? – The111
Es scheint, maxLen wird nie aktualisiert und wird jedes Mal als 0 ausgegeben. Ich habe ein paar Probleme, da ich für beide maximale Länge UND Summe <= k überprüfen muss. – FlameDra