Anzahl der Paare deren Summe = 0 ergibt berechnen

[lennero]

Hallo.
Ich soll eine Methode schreiben, die die Anzahl der Paare berechnet, deren Summen null ergeben. Das Array darf als sortiert angenommen werden. Die binäre suche oder maps dürfen nicht verwendet werden. Die worst-case Zeitkomplexität soll O(N) sein.

Hier ist eine simple Lösung mit einer Zeitkomplexität von O(N^2)

public static int twoSumNaive(int[] a)
    {
        int count = 0;
        for(int i = 0; i < a.length; i++)
        {
            for(int j = i + 1; j < a.length; j++)
            {
                if(a[i] + a[j] == 0) count++;
            }
        }
        return count;
    }

Die Methode deckt alle möglichen Kombinationen ab. Für ein Array

[-1, -1, -1, 0, 0, 0, 0, 1, 3, 3]

gibt es 9 Paare die in Summe 0 ergeben.

Ich habe die Methode dann so verändert, dass die Suche nach Paaren linear verläuft.

public static int twoSumFast(int[] a)
    {
        int count = 0;
        int i = 0;
        int j = a.length - 1;
        while(i < j)
        {
            if(-a[i] > a[j]) i++;
            else if(-a[i] < a[j]) j--;
            else
            {
                //if both indices point to a zero, add the number of possible combinations to count
                if(a[i] == 0 && a[j] == 0)
                {  
                    //binomial coefficient n!/k!*(n - k)! for n = j - 1 + 1 (number of zeros) and k = 2 (ways to pick 2 numbers based on indices)
                    count += ((j - i + 1) * (j - i)) / 2;
                    break;
                }
               
                int countRight = 1;
                int countLeft = 1;
                //count the number of values left of j that are equal to a[j] and right of i that are equal  to a[i]
                while(a[j - 1] == a[j])
                {
                    countRight++;
                    j--;
                }
                while(a[i + 1] == a[i])
                {
                    countLeft++;
                    i++;
                }
                count += countLeft * countRight;
                i++;
                j--;
            }
        }
        return count;
    }

Mir kommt die Lösung aber etwas zu kompliziert für so eine (scheinbar) einfache Aufgabe vor. Gibt es hierfür eine einfachere Lösung mit einem eleganteren Algorithmus (der natürlich die Anforderungen erfüllt)? Wichtig ist, dass alle Kombinationen abgedeckt werden. Das heißt beide Methoden oben sollen den selben Wert zurückgeben.