力扣3115题解：数组中质数位置的最大差值算法详解

一、问题描述

给定一个整数数组nums，要求找出数组中所有质数元素的最小位置和最大位置之间的差值。如果数组中只有一个或没有质数，则返回0。

二、解题思路

1. 质数判断：首先需要判断一个数是否为质数

2. 位置记录：遍历数组，记录所有质数元素的位置

3. 差值计算：找出最左和最右质数位置，计算它们的差值

三、完整代码

class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        int min_prime = INT_MAX;  // 初始化最小位置为最大整数
        int max_prime = -1;       // 初始化最大位置为-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;
                }
            }
        }
        
        // 返回结果：如果有多个质数则返回差值，否则返回0
        return found && (min_prime != max_prime) ? max_prime - min_prime : 0;
    }
    
private:
    // 质数判断函数
    bool isPrime(int num) {
        if (num <= 1) return false;  // 1及以下的数不是质数
        if (num == 2) return true;   // 2是质数
        if (num % 2 == 0) return false;  // 排除偶数
        
        // 检查3到sqrt(num)之间的奇数
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
};

四、代码解析

1. 主函数maximumPrimeDifference：

• 初始化min_prime为INT_MAX，max_prime为-1

• 遍历数组，使用isPrime函数判断每个元素是否为质数

• 维护最小和最大质数位置

• 最后根据条件返回差值或0

2. 辅助函数isPrime：

• 处理特殊情况：1及以下的数、2、偶数

• 使用优化方法检查奇数因子，只需检查到√num