Znajdź ilość par

Twoje rozwiązanie ma złożoność obliczeniową O(n^2), da się to zrobić w O(n).

Ok, czyli jest słabe. Podpowiedz mi tylko czy z wykorzystaniem samej tablicy czy tak jak wspomniałem kolekcji i streama albo konkretnej implementacji kolekcji i wykorzystanie jej właściwości?

Pomyśl o dodatkowej strukturze danych, aby zapisywać odwiedzone już elementy. Jeśli elementy są z przedziału 0 do N-1, to można zastosować trick pozwalający na nie korzystanie z dodatkowej pamięci.

Hint: na Codility zapomnij o streamach Javowych i innych luksusach, myśl w kategoriach algorytmów i struktur danych.

Mapa i int jako klucz i ilość wystąpień jako aktualizowana wartość?

Java to nie moja bajka, ale naskrobałem coś takiego: https://ideone.com/ALmcTJ

Klasyczne zadanie na hash mape

MarekR22 napisał(a):

Java to nie moja bajka, ale naskrobałem coś takiego: https://ideone.com/ALmcTJ

Tzn. da się to zrobić na HashMapie, ale ignorujesz powtórzenia. Według twojego rozwiązania dla tablicy [A, B, C] gdzie A=B=C=1 jest tylko jedna para, podczas gdy są trzy pary (A,B; A,C; B,C) czyli końcówka powinna wynosić:

        return m.values().stream()
                    .mapToInt(i -> i-1)
                    .sum();

A nie czasami tak?

class Task
{
    static long countPairs(int[] a)
    {
        int result = 0;
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int x : a)
        {
            result += m.compute(x, (key, val) -> (val == null) ? 0 : val + 1);
        }
        return result;
    }
}

Bo jeżeli mamy np. int[10] i każdy element tablicy jest równy to możemy stworzyć łącznie sum = 9+8+...+0 par spełniających warunek i<j & int[i]==int[j].