454. 4Sum II

LeetCode задача 454

Задача

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

Подсказки

Используйте хэш-таблицу для ускорения решения.

Подход

1. Создание хэш-таблицы: Сначала создайте хэш-таблицу, которая будет хранить суммы пар чисел из массивов A и B.
2. Подсчет сумм: Для каждой пары (i, j) из A и B, увеличьте соответствующий элемент хэш-таблицы на 1.
3. Поиск в хэш-таблице: Для каждой пары (k, l) из C и D, проверьте, существует ли -(C[k] + D[l]) в хэш-таблице. Если да, увеличьте счетчик на соответствующее значение из хэш-таблицы.
4. Возврат результата: Верните значение счетчика.

Этот метод является простым и эффективным с точки зрения времени.

Алгоритм

1. Инициализируйте counter = 0 и хэш-таблицу sums.
2. Посчитайте суммы для всех пар (i, j) из A и B и сохраните их в sums.
3. Переберите все пары (k, l) из C и D и проверьте наличие -(C[k] + D[l]) в sums.

Решение

from collections import defaultdict

def fourSumCount(A, B, C, D):
    counter = 0
    sums = defaultdict(int)
    
    # Считаем суммы для всех пар из A и B
    for i in A:
        for j in B:
            sums[i + j] += 1
            
    # Проверяем наличие -(C[k] + D[l]) в хэш-таблице
    for k in C:
        for l in D:
            if -(k + l) in sums:
                counter += sums[-(k + l)]
                
    return counter