LeetCode 2523题解：寻找区间内最小间隔质数对（C++代码）
一、题目解读
LeetCode 2523题要求在一个给定的整数区间 [left, right] 内，找到间隔最小的两个质数（即相邻质数的差值最小），并返回这对质数。若区间内不存在两个质数，则返回 [-1, -1]。题目考察质数筛选算法与区间内最优对查找的逻辑。
二、解题思路
采用经典埃拉托斯特尼筛法（Sieve of Eratosthenes）生成质数，并结合双指针思想寻找最小间隔对。核心思路分为三步：
1. 质数筛选：通过筛法标记 [0, right] 内所有非质数，构建质数列表。
2. 区间质数收集：从 left 开始遍历筛后数组，保留区间内的质数。
3. 最小间隔查找：遍历质数列表，用双指针比较相邻质数差值，记录最小间隔对。
三、解题步骤
1. 初始化筛法：创建布尔数组 is_prime，标记所有数默认为质数（true），排除 0 和 1。
2. 执行筛法：从 2 开始，若 i 是质数，则将 i 的倍数（i², i²+i,...）标记为非质数（false）。
3. 收集区间质数：从 max(2, left) 到 right 遍历，若 is_prime[i] 为 true，加入质数列表 primes。
4. 查找最小间隔：
若 primes 长度不足 2，直接返回 [-1, -1]。
用双指针 i 遍历 primes，计算相邻质数差 diff，更新最小差 min_diff 及对应质数对 result。
5. 返回结果：输出最小间隔质数对 result。
四、代码与注释
class Solution {
public:
vector<int> closestPrimes(int left, int right) {
// 使用埃拉托斯特尼筛法找出所有质数
vector<bool> is_prime(right + 1, true);
is_prime[0] = is_prime[1] = false; // 排除0和1
for (int i = 2; i * i <= right; ++i) { // 优化筛法边界：i² <= right
if (is_prime[i]) { // 若i是质数
for (int j = i * i; j <= right; j += i) { // 标记i的倍数
is_prime[j] = false;
}
}
}
// 收集区间内的所有质数
vector<int> primes;
for (int i = max(2, left); i <= right; ++i) {
if (is_prime[i]) {
primes.push_back(i); // 保留left及以上的质数
}
}
// 寻找最小间隔的质数对
if (primes.size() < 2) { // 质数不足2个，返回默认值
return {-1, -1};
}
int min_diff = INT_MAX; // 初始化最小差为最大值
vector<int> result;
for (int i = 1; i < primes.size(); ++i) {
int diff = primes[i] - primes[i-1];
if (diff < min_diff) { // 更新最小差及对应质数
min_diff = diff;
result = {primes[i-1], primes[i]};
}
}
return result;
}
};注释说明：
● 筛法优化：仅需遍历至 i * i <= right，避免重复标记。
● 区间处理：从 max(2, left) 开始收集质数，确保 left 可能为 1 时的正确性。
● 双指针查找：通过 primes[i] - primes[i-1] 直接计算相邻差，简化逻辑。
五、总结
本解法通过埃拉托斯特尼筛法高效预处理质数，再在区间内通过双指针线性查找最优解，时间复杂度 O(n log log n)（筛法） + O(n)（区间遍历），空间复杂度 O(n)（质数列表）。关键在于：
1. 筛法的边界优化：减少不必要的循环次数。
2. 区间处理的灵活性：确保 left 可能小于 2 时的兼容性。
3. 双指针的简洁性：避免嵌套循环，提升效率。
适用于对时间复杂度要求较高的场景，是解决区间质数查找问题的经典模板。
原创内容 转载请注明出处
