平衡的小队

按下左边的箭头，点个赞吧！


这道题有两种做法：

• 队列
• 双指针

虽然这两种做法不同，思路却是相同的
本人的第一想法是排个序，在双重循环一个找$i$，一个找$j$
时间复杂度：$O(n^2)$ （超时qaq）
超时代码：

#include <iostream>
#include <algorithm>
using namespace std;
int a[200005];
int main() {
    int n, k, maxn = -1;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (a[j] - a[i] <= k) maxn = max(maxn, j - i + 1);
        }
    }
    cout << maxn;
    return 0;
}

咱们一起来想想正解：
排完序后，这个数组是有序的，那么就可以设l为左指针，r为右指针，
当$a[r] - a[l] > k$的时候把l往右挪（让相差减少）；
当$a[r] - a[l] \le k$的时候把r往右挪（让相差大一点，让数量变多）
这就是正解的思路。
正解代码：

#include <iostream>
#include <algorithm>
using namespace std;
int a[200005];
int main() {
    int n, k, l = 1, r = 1, maxn = -1;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    while (r != n) {
        if (a[r] - a[l] <= k) {
            maxn = max(maxn, r - l + 1);
            r++;
        }
        else if (a[r] - a[l] > k) l++;
    }
    cout << maxn;
    return 0;
}