c++ - 计算第一个元素和最后一个元素的绝对差小于等于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)，但由于这是一个无限循环，因此当然会超时:

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++;
}

干杯!