Вопрос интервью: три массива и O (N * N)

Question

Предположим, у нас есть три массива длины N , которые содержат произвольные числа типа long.Тогда нам дают число M (того же типа), и наша миссия состоит в том, чтобы выбрать три числа A , B и C по одному от каждого массива (другими словами A следует выбирается из первого массива, B из второго и C из третьего), поэтому сумма A + B + C = M .

Вопрос: Можем ли мы выбрать все три числа и получить временную сложность O (N ² ) ?

---

Иллюстрация:

Массивы:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

И M нам дали 19 .Тогда наш выбор будет 8 от первого, 4 от второго и 7 от третьего.

Answer 1

Как насчет:

for a in A
 for b in B
  hash a*b

for c in C
 if K-c is in hash
   print a b c

Идея состоит в том, чтобы хэшировать все возможные пары в A и B. Далее для каждого элемента в C посмотрите, присутствует ли остаточный zum в хэше.