Задача четырех сумм найти туплетов - сложность пространства - PullRequest
Новая
       13

Задача четырех сумм найти туплетов - сложность пространства

0 голосов
/ 03 ноября 2018

Я работаю над вопросом ниже интервью:

Учитывая четыре списка целых значений A, B, C, D, подсчитайте, сколько кортежей (i, j, k, l) существуют такие, что A [i] + B [j] + C [k] + D [l] равно нулю.

Чтобы облегчить задачу, все A, B, C, D имеют одинаковую длину N где 0 ≤ N ≤ 500. Все целые числа находятся в диапазоне от -228 до 228 - 1 и результат гарантированно будет максимум 231 - 1.

Пример:

Введите:

A = [1, 2]

B = [-2, -1]

C = [-1, 2]

D = [0, 2]

Выход: 2

Ниже приведен код , и я не могу понять, почему сложность пространства равна O (n ^ 2)? Мы используем только одну карту, так что это должно быть O (N) пространство сложности? 

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();

    for(int i=0; i<C.length; i++) {
        for(int j=0; j<D.length; j++) {
            int sum = C[i] + D[j];
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
    }

    int res=0;
    for(int i=0; i<A.length; i++) {
        for(int j=0; j<B.length; j++) {
            res += map.getOrDefault(-1 * (A[i]+B[j]), 0);
        }
    }

    return res;
}

Ответы [ 2 ]

0 голосов
/ 03 ноября 2018

Допустим, C.length = D.length = N. У вас есть петля внутри петли. Это означает, что в первой части алгоритма вы вызываете map.put функцию N*N раз. Это дает вам уже O(N^2). Когда вы используете HashMap, вы можете предположить, что get и put операции «стоят» постоянное время.

Вторая часть более или менее одинакова. Это дает вам O(N^2 + N^2) = O(N^2).

0 голосов
/ 03 ноября 2018

зависит от длины входных массивов A, B, C, D

если мы примем каждый массив длиной N, это означает у нас

O (NxN) для первого вложенного цикла O (NxN) для второго вложенного цикла

следовательно, мы имеем O (NxN) + O (NxN) = O (2xN ^ 2) 

= O(N^2)

Мы используем только одну карту, так что это должно быть O (n) пространство сложности?

НЕТ, вы помещаете в карту O (N ^ 2) раз, так как это вложенный цикл

...