Учитывая отсортированный массив, выведите все триплетытакой, что ab = c

Question

Учитывая отсортированный массив, выведите все триплеты, так что a-b = c. Код, который я пробовал до сих пор, приведен ниже; но есть следующие тестовые случаи -

-12 = -7 - 5
-12 =  3 - 15
 -7 = -4 - 3
 -7 =  3 - 10
 -7 =  9 - 16
 -4 =  5 - 9
  3 = -4 - -7
  5 = -7 - -12
  5 = 15 - 10 
 10 = 3 - -7 
 10 = 15 - 5
15 = 3 - (-12)
16 = 9 - (-7)

пока печатает только моя программа-

-12 = -7 - 5
 -7 = -4 - 3
 -12 = 3 - 15
 -7 = 3 - 10
 -4 = 5 - 9
 -7 = 9 - 16
 5 = 15 - 10

означает только разницу в абс! Любое предложение очень поможет!

void binder(int*a, int n) {
    int i;
  for (i = 0; i < n; i++) {
    int current = a[i];
    int left = 0;
    int right = n-1;
    while (left < right) {
      if ( left == i ) {
        left++;
        continue;
      }


if (right == i) {
        right--;
        continue;
      }



if (a[left] + a[right] < current) {
        left++;
      } else if (a[left] + a[right] > current) {
        right--;
      } else {
        printf("\n %d = %d - %d",a[left],current, a[right]);
        left++;
        right--;
      }
    }
  }
}



int main() {
  int a[] = {-12, -7, -4, 0, 3, 5, 9, 10, 15, 16};
  binder(a, 10);
  return 0;
}

Answer 1

Как насчет этого:

HashTable table;
for b = 0 to n-1:
    for c = 0 to n-1:
        table[b + c] = <b, c>
    end for
end for

for a = 0 to n-1:
    if table[a] exists and (<b, c> in table[a] where b != a and c != a) then:
        output <a, b, c>
    end if
end for

Итак, если мы рассмотрим «a = b + c», для каждой (b, c) пары значений мы поместим это в хеш-таблицу, связав ее с парой (b, c) [O (n ^ 2)].

Затем мы снова просматриваем массив, и если значение появляется в хеш-таблице, и связанные пары предназначены для разных индексов, то мы нашли новую запись (переставляя термины обратно в "ab = c") , Этот шаг O (n), в результате чего решение O (n ^ 2) в целом.

Я думаю, что мы можем рассматривать этот вопрос как вариант решения задачи «найти пары значений в массиве с суммой до S для фиксированной S».

Answer 2

Это решение O (n ^ 3), но оно должно работать.

void binder(int*a, int n)
{
    for(int left = 0; left < n; left++)
    {
        for(int right = 0; right < n; right++)
        {
            for(int result = 0; result < n; result++)
            {
                if(left != right && left != result && result != right && a[left] - a[right] == a[result])
                    printf("\n %d = %d - %d", a[result], a[left], a[right]);
            }
        }
    }
}

Answer 3

Если они отсортированы (и, как указал Хеннинг, ab = c - это то же самое, что a = b + c), вы можете начать с наименьшего b и c и добавить их, что должно привести к наименьшему a,Теперь, увеличивая b или c, a может только увеличиваться, так что вам не нужно оглядываться назад.

Если вы составите таблицу b и c и их суммы (которая должна быть одной из a):

c\ b:-12    3   4   5   7  10  15 16  
-12: -24, -19, -9, -7, -3, -2,  3, 4
 -7:  -9,  -4,  6,  8, 12, 13, 18, 
  3:  -8,  -3,  7,  9, 13, 14, 19, 
  5:  -7,  -2,  8, 10, 14, 15, 
  9:  -5,   0, 10, 12, 16, 
 10:  -2,   3, 13, 15,  
 15:   3,   8, 18,  
 16:   4,   9, 19,  

вы увидите, что я опустил значения в правом нижнем углу,поскольку предыдущее значение (слева) уже превысило максимум a (15), поэтому более высокое значение не может совпадать.

Конечно, для такого небольшого числа уравнений вы тратите гораздо больше времени на размышления об оптимизации, чем на отсутствие лишних вычислений.Для гораздо больших наборов значений может быть полезно оптимизировать.

Answer 4

Похоже, что в тестовом примере также отсутствует триплет:

9 =  5 - (-4)

Попробуйте изменить печать с:

printf("\n %d = %d - %d",a[left],current, a[right]);

на:

printf("\n %d = %d - %d",a[left],current, a[right]);
printf("\n %d = %d - %d",a[right],current, a[left]);

Answer 5

вы пропустили еще одну итерацию / цикл в вашем коде. так как вы используете стратегию грубой силы, анализ говорит, что это займет O (n ^ 3) пространства, а сложность вашего кода кажется O (n ^ 2). Вот случай, который поможет вам понять. вы проверяете: a = b-c и вы пропустите проверку для: c = b-a