【力扣3115题解】数组中质数最大差值的求解（C++代码详解）

一、题目解读

力扣3115题要求在一个整数数组中，找出两个质数之间的最大差值。若数组不存在质数，则返回0。题目核心在于高效筛选质数，并计算其索引差值的最大值，需兼顾时间与空间复杂度。

二、解题思路

参考代码采用“单次遍历+质数判定优化”策略：

1. 初始化最小质数索引min_prime为INT_MAX，最大质数索引max_prime为-1，标记变量found记录是否找到质数。

2. 遍历数组，调用isPrime()判断当前数是否为质数。

3. 若找到首个质数，更新min_prime和max_prime；后续质数更新时，仅调整两者极值。

4. 最终根据found状态和索引差返回结果。

关键在于通过单次遍历避免重复计算，并利用优化后的质数判断函数减少时间消耗。

三、解题步骤

1. 初始化变量：设置min_prime、max_prime及found。

2. 遍历数组：对每个元素调用isPrime()。

3. 更新索引：

○ 若为质数且未找到首个质数，记录min_prime和max_prime；

○ 若已找到，仅更新极值索引。

4. 计算差值：根据found状态判断是否返回max_prime - min_prime或0。

四、代码及注释

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int min_prime = INT_MAX;  // 记录最小质数的位置
        int max_prime = -1;       // 记录最大质数的位置
        bool found = false;       // 标记是否找到质数
        
        for (int i = 0; i < nums.size(); ++i) {
            if (isPrime(nums[i])) {
                if (!found) {
                    min_prime = i;
                    max_prime = i;
                    found = true;
                } else {
                    if (i < min_prime) min_prime = i;
                    if (i > max_prime) max_prime = i;
                }
            }
        }
        
        return found && (min_prime!= max_prime)? max_prime - min_prime : 0;
    }
    
private:
    bool isPrime(int num) {
        if (num <= 1) return false;          // 非质数
        if (num == 2) return true;           // 特殊处理2
        if (num % 2 == 0) return false;      // 偶数非质数（除2外）
        
        for (int i = 3; i * i <= num; i += 2) {  // 仅检查奇数因子
            if (num % i == 0) return false;
        }
        return true;
    }
};

五、总结

该解法通过单次线性遍历结合高效质数判定，实现O(n√n)时间复杂度。关键在于：

1. 利用标记变量减少分支判断；

2. 质数判定函数通过排除偶数、缩小循环范围优化性能；

3. 边界条件（如空数组、无质数）通过found自然处理。