当前位置：首页 > 力扣 > LeetCode 2523题解：寻找区间内最小间隔质数对（C++代码）

LeetCode 2523题解：寻找区间内最小间隔质数对（C++代码）

1天前

一、题目解读

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] 直接计算相邻差，简化逻辑。