Zadanie - Dwie sumy.

Question

Mam prośbę o pomoc w zrozumieniu zadania:

Zad.: Mając tablicę liczb całkowitych, zwróć indeksy dwóch liczb w taki sposób, aby sumowały się do określonej wartości docelowej. Możesz założyć, że każde wejście będzie miało dokładnie jedno rozwiązanie i nie możesz użyć tego samego elementu dwa razy.

i napisałem taki kod:

        int[] numbers = {2, 7, 11, 15};
        int target = 18;

        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (((numbers[i] + numbers[j])) == target) {
                    System.out.println("indeksy: [" + i + "] i [" + j + "]");
                }
            }
        }

Czy coś muszę zmienić w kodzie?

Answer 1

Zadanko powiedzmy jest dobrze zrobione, ale bardzo nieefektywnie... ogromna złożoność obliczeniowa z racji zagnieżdzenia pętli for w for, co wydłusza liczbę operacji praktycznie do kwadratu liczby elementów,.

W twoim rozwiązaniu dla  każdej pary elementów w tablicy sprawdzasz  czy ich suma równa się docelowej wartości.

Zdecydowanie tutaj warto posiłkować się np. wyrzkoystaniem mapy w Javie https://docs.oracle.com/javase/8/docs/api/java/util/Map.html intefejs ten jest dla kolekcji zawierającej klucz-> unikalny i przypisana mu wartość,

Wtedy robisz tylko jedno przejście iteracyjne ze sprawdzeniem realnie, czy dany element istnieje w mapie- co jest potwierdzeniem, że wystąpił więcej niż raz.

Np. 

    public int[] twoindexSum(int[] nums, int target) {
        Map<Integer, Integer> numIndexMap = new HashMap<>();

        Optional<int[]> result = IntStream.range(0, nums.length)
                .boxed()
                .filter(i -> numIndexMap.containsKey(target - nums[i]))
                .map(i -> new int[]{numIndexMap.get(target - nums[i]), i})
                .findFirst();

        return result.orElse(new int[0]);
    }

tu masz jeszcze referencje do wykorzystania  autobozxingu z metody https://www.geeksforgeeks.org/intstream-boxed-java, natomiast pozostałe funkcje pośrednie jak i końcowe warto przestudiować. 

Czym jest Optional to także można wyjasnić: 
https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html

Co jeszcze? A no przemyśl sytuacje, że zadanie twoje jest prawdziwe i poprawne, kiedy liczba elementów jest równa 2, nie więcej, dodatkowo, jeśli nie ma elementów warto zwrócić informacje np.  o braku rozwiązania, dla konkretnego zestawu testowego