c - 相差至少 K 的数字对的数量

Question

给定n(数组中的项数)和k(正数)和数组arr[]，预计查找数组中的对数，使得它们的差异至少为 k。
例如:
输入

7 2  
2 4 3 5 6 1 7

输出

15

所以我的方法是:

int main()
{
   long long int n,k;
   scanf("%lld %lld",&n,&k);
   long long int a=0,arr[n];
   while(a<n)
   {
    scanf("%lld",&arr[a]);
    a++;
   }
   quicksort(arr,0,n-1);//sorting the array
   long long int i=n-1,j=0,ans=0;//two-pointer method
   while(i>0)
   {
    if(arr[i] - arr[j] >= k && j < i)
    {
        ans ++;
        j++;
    }
    else
    {
        i--;
        j = 0;
    }
   }
   printf("%lld",ans);
    return 0;
}

但是该解决方案超出了较大测试用例的时间限制。有什么可能的改进吗？

Answer 1

您可以在这个问题中使用二分搜索。对数组进行排序后，您可以通过binary searching找到每个元素x的差异大于K的对。对于K+x。找到索引i后，其后面的元素的值都等于或大于K+x，您就可以轻松解决问题。

total = 0
sort(arr)
for each x in arr:
   i = lower_bound(K+x)
   total += arr.size - i