题解 | #相差不超过k的最多数# ✅✅✅ 双指针满分解法

关键词：双指针 / 滑动窗口

核心思想：使用滑动窗口算法通过动态调整窗口的大小，遍历所有符合条件的连续子序列，求得最大连续子序列的长度。

解题步骤：

1. 排序：首先对数组进行排序，以方便后续检查相邻元素之间的差值是否满足条件。
2. 滑动窗口：使用滑动窗口技术来找到满足条件的最长子序列。这里使用两个指针 l（左指针）和 r（右指针），初始时都指向数组的第一个元素。
3. 条件判断：当 nums[r] - nums[l] 小于等于 k 时，说明当前窗口内的所有数都满足条件，此时更新答案ans 并移动右指针 r；否则，移动左指针 l 以缩小窗口，直到窗口内的数再次满足条件。
4. 结果输出：最终输出答案 ans，即满足条件的最大数的数量。

算法复杂度：时间复杂度O(nlogn)，空间复杂度O(n)。

代码示例：C++、Java代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k; 
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    // 对数组进行排序，排序后可以方便地检查相邻元素之间的差值是否满足条件
    sort(nums.begin(), nums.end());

    int l = 0, r = 0, ans = 0;  // 初始化左指针 l、右指针 r 和答案 ans
    // l 和 r 表示当前窗口的左右边界，ans 用于记录满足条件的最大数的数量

    // 使用滑动窗口技术
    while (r < n)   // 当右指针 r 没有超出数组边界时继续循环
        // 检查当前窗口内的数是否满足条件
        if (nums[r] - nums[l] <= k) {  // 如果当前窗口内的数满足条件
            ans = max(ans, r - l + 1);  // 更新答案，计算当前窗口内的数的数量
            r++;  // 移动右指针，尝试扩展窗口
        } else l++;  // 如果不满足条件，移动左指针，缩小窗口

    cout << ans << endl;
    return 0;
}

Java：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 对数组进行排序
        Arrays.sort(nums);

        int l = 0, r = 0, ans = 0;  // 初始化左指针 l、右指针 r 和答案 ans

        // 使用滑动窗口技术
        while (r < n) {  // 当右指针 r 没有超出数组边界时继续循环
            if (nums[r] - nums[l] <= k) {  // 如果当前窗口内的数满足条件
                ans = Math.max(ans, r - l + 1);  // 更新答案，计算当前窗口内的数的数量
                r++;  // 移动右指针，尝试扩展窗口
            } else {
                l++;  // 如果不满足条件，移动左指针，缩小窗口
            }
        }

        System.out.println(ans);
    }
}