По 4 несортированным массивам найти все возможные четверки с суммой <m

Question

Учитывая четыре массива одинаковой длины, которые не отсортированы, и в них есть уникальные элементы, но элементы массива могут конфликтовать, поэтому нас попросили выбрать один элемент из каждого массива и выполнить это условие "x1 + x2 + x3 + x4

Можем ли мы сделать что-то лучше, чем отсортировать все массивы и сделать это в O (n ^ 3 * logn)?

Answer 1

1. Создание массива со всеми суммами между элементами от x1 и x2.Это будет иметь O (n ^ 2) элементов.Давайте назовем это arr0
2. Сделайте то же самое для x3 и x4.Давайте назовем это arr1
3. Сортировать оба

4. Теперь мы уменьшили задачу до определения суммы сумм

   p0 = 0
   p1 = arr1.length - 1
   qty = 0
   while(p0 != p1)
       while(p1 >= 0 and arr0[p0] + arr1[p1] >= m) p1--;
       if (p1 <= p0) break;
       qty += p1
       po++
   

Этот небольшой алгоритм решит это в O (length (arr0) + length (arr1)), так как указатель p1 всегда уменьшается, а p0 всегда увеличивается, и для каждого цикла мы всегда увеличиваем или уменьшаем один из них

В целом это дает нам O (n ^ 2) для генерации пар, O (n ^ 2 * log n ^ 2) для их сортировки и O (n ^ 2) для подсчета четверок.