Алгоритмы. Задача "Count Good Triplets".

Оригинал: 1534. Count Good Triplets

Условия

Дано массив целых чисел arr и три целых числа a, b, c. Требуется определить количество подходящих триплетов.

Триплет(arr[i], arr[j], arr[k]) считается подходящим, если одновременно выполняются условия:

• 0 ≤ i < j < k < arr.length;
• |arr[i] − arr[j]| ≤ a;
• |arr[j] − arr[k]| ≤ b;
• |arr[i] − arr[k]| ≤ c.

Здесь |x| обозначает абсолютное значение числа x.

Верните количество подходящих триплетов.

Пример 1

Ввод: arr = [3, 0, 1, 1, 9, 7], a = 7, b = 2, c = 3 Вывод: 4 Пояснение: Существует 4 хорошие тройки: (3,0,1), (3,0,1), (3,1,1) и (0,1,1).

Пример 2

Ввод: arr = [1, 1, 2, 2, 3], a = 0, b = 0, c = 1 Вывод: 0 *Пояснение: Ни одна тройка не удовлетворяет всем условиям.

Ограничения

• 3 <= arr.length <= 100
• 0 <= arr[i] <= 1000
• 0 <= a, b, c <= 1000

Решение с тремя циклами

function countGoodTripletsNaive(arr, a, b, c) {
	  let count = 0;
	  const n = arr.length;
	  for (let i = 0; i < n - 2; i++) {
	    for (let j = i + 1; j < n - 1; j++) {
	      if (Math.abs(arr[i] - arr[j]) > a) continue;
	      for (let k = j + 1; k < n; k++) {
	        if (
	          Math.abs(arr[j] - arr[k]) <= b &&
	          Math.abs(arr[i] - arr[k]) <= c
	        ) {
	          count++;
	        }
	      }
	    }
	  }
	  return count;
}

Мой вариант - идём "прямо" и проходимся для каждого элемента триплета циклом и проверяем на условия. Алгоритмическая сложность - по скорости - O(n³), память O(1).

Так как из условия

0 <= i < j < k < arr.length

следует то, что индексы в триплете должны быть по возрастающей, цикл по первому элемента в триплете должен гарантировать, что для двух следующих элементов есть значения, поэтому он должен идти только до длинны переданного массива - 3, тоесть до n - 3:

for (let i = 0; i < n - 2; i++)

Затем мы сразу идём по следующему цилу для второго элемента триплета j. По аналогии с первым цилом, мы должны быть уверены, что для третьего элемента триплета у нас есть значение, поэтому мы ограничиваем количество прохождений по цилклу, гарантируя, что есть следующий элемент, тоесть до n - 2:

for (let j = i + 1; j < n - 1; j++)

Теперь мы можем проверить первое условие, чтобы понять, нужно ли нам двигаться к цилу для третьего элемента триплета

|arr[i] - arr[j]| <= a

Lля этого проверяем модуль разности элементов массива,

if (Math.abs(arr[i] - arr[j]) > a) continue

и если она больше переданного числа a, то просто продолжаем цикл для второго элемента триплета j.

Для третьяего элемента мы уже не ограничиваем длину прохождения, так как после него нам не нужны гарантированные значения:

for (let k = j + 1; k < n; k++)

Внутри мы проверяем для каждой итерации оставшиеся условия

Math.abs(arr[j] - arr[k]) <= b && 
Math.abs(arr[i] - arr[k]) <= c

и если они true, то увеличиваем count - count++

Пример прохождения (кратко)

Для arr = [3,0,1,1,9,7], a=7, b=2, c=3:

1. i=0 (arr[i]=3)
   • j=1 (arr[j]=0): ∣3−0∣=3≤7 → идём в k
     • k=2 (1): ∣0−1∣=1 ≤ 2 , ∣3−1∣=2 ≤ 3 → нашли (3,0,1)
     • k=3 (1): аналогично → нашли
     • k=4,5: условия b или c нарушаются → пропускаем
   • j=2,3 (arr[j]=1): ∣3−1∣=2≤7 → проверяем k…
   • и так далее для всех j,k.
2. i=1 (arr[i]=0), i=2, i=3 — аналогично.

Итог—4 триплета.