Подсчитайте общее количество пар чисел, которые имеют разность K

Question

Вот как я решить эту проблему:

void solve (int *input, int N, int K, int& count) { 
    std::sort (input, input + N); 
    for (int i = 0; i < N; i++) { 
     int find_me = input[i] + K; 
     if (std::binary_search (input + i + 1, input + N, find_me)) 
      count++;   
     else 
      break; 
    } 
} 

input имеет integer значения, которое гарантированно будет unique и > 0, N является количество элементов ,

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

Answer 1

Я не уверен, правильно ли я понял коды, но мне кажется, что если в массиве не существует числа со значением input, ваш цикл будет завершен с этим break. Я думаю, вот в чем проблема.

Answer 2

Есть две проблемы с вашим кодом. Во-первых, часть else break;if должна уйти, чтобы избежать преждевременного выхода из цикла for. Во-вторых, вы запускаете один за концом цикла на последней итерации. Условие завершения цикла должно быть i < N - 1.

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