Подсчитать подпоследовательности с абсолютной разницей первого и последнего элемента меньше <= K

Question

Я столкнулся с этой проблемой в хакатоне, но не мог понять, где я ошибался.

Постановка проблемы была

Count the number of subsequences in an array where the difference of the first and last element is <= K

Each subsequence is contiguous

Input: 11 5 2 15 25
Output: 6

Explanation: {11}, {5}, {2}, {15}, {25}, {5, 2}

Я полагаю, что они рассматривали один элемент в качестве действительной подпоследовательности, поэтому что я пытался вернуть длину массива + количество.

int getCount(int *a, int n, int k){
   sort(a, a + n);
   int c = 0;
   for(int i=0; i<n; i++){
       int j = i + 1;
       while(j < n and a[j] - a[i] <= k){
           c+=1;
           j+=1;
       }
   }
   return n + c;
}

Я пробовал сортировку, но время все равно истекло!

Answer 1

вы используете подход O (n n), вместо этого используйте подход O (n logn) для преодоления проблемы TLE, поэтому вы отсортировали массив, поэтому просто примените двоичный поиск для каждого элемента, чтобы найти элемент наибольшего расстояния, имеющий разница меньше или равна k, поэтому она работает на O (nlogn); значит решено !! СПАСИБО !!!

Answer 2

Ничего, что я вижу здесь, не является неправильным со сложностью, оно должно быть O (n * n), но, конечно, оно истечет, поскольку это бесконечный цикл:

while(j < n and a[j] - a[i] <= k) c += 1;

Исправление:

while(j++ < n and a[j] - a[i] <= k) c += 1;

ИЛИ

while(j < n and a[j] - a[i] <= k) {
   c += 1;
   j++;
}

---

Также вы можете изменить сравнение с более низкого или равного на более низкое

Окончательный вариант:

while(j < n and a[j] - a[i] < k) {
   c += 1;
   j++;
}

Ура!