2024-11-30：质数的最大距离。用go语言，给定一个整数数组 nums，请找出两个（可以是相同的）质数在该数组中的下标之间的最大距离。

提示：

nums的长度在[1,3*10^5]之间。

nums的每个元素的值在[1,100]。

输入保证 nums 中至少有一个质数。

输入： nums = [4,2,9,5,3]。

输出： 3。

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

答案2024-11-30：

chatgpt

题目来自leetcode3115。

大体步骤如下：

1.定义一个函数 maximumPrimeDifference(nums []int) int 用于计算质数的最大距离。其中，根据给定的质数列表 primes 和数组 nums：

• 创建一个 map primeSet 用于存储质数的出现情况。

• 遍历 nums 数组，找到第一个质数的下标，并记录在变量 first 中。

• 再次遍历 nums 数组，找到最后一个质数的下标，并记录在变量 last 中。

• 返回最后一个质数的下标与第一个质数的下标之间的距离。

2.在主函数 main 中，定义一个示例数组 nums := []int{4, 2, 9, 5, 3}。

3.调用 maximumPrimeDifference(nums) 函数，并输出结果。

总体时间复杂度为 O(n), 其中 n 为数组 nums 的长度。

总体空间复杂度为 O(1)，并不随输入规模变化。

Go完整代码如下：

package main

import (
	"fmt"
)

func maximumPrimeDifference(nums []int) int {
	primes := []int{2, 3, 5, 7, 11,
		13, 17, 19, 23, 29,
		31, 37, 41, 43, 47,
		53, 59, 61, 67, 71,
		73, 79, 83, 89, 97}
	primeSet := make(map[int]struct{})
	for _, v := range primes {
		primeSet[v] = struct{}{}
	}
	n := len(nums)
	first := 0
	for i := 0; i < n; i++ {
		if _, ok := primeSet[nums[i]]; ok {
			first = i
			break
		}
	}
	last := 0
	for i := n - 1; i >= 0; i-- {
		if _, ok := primeSet[nums[i]]; ok {
			last = i
			break
		}
	}
	return last - first
}

func main() {
	nums := []int{4, 2, 9, 5, 3}
	fmt.Println(maximumPrimeDifference(nums))
}

Rust完整代码如下：

fn maximum_prime_difference(nums: Vec<i32>) -> i32 {
    let primes = [
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
        31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97,
    ];

    let prime_set: std::collections::HashSet<i32> = primes.iter().cloned().collect();
    let n = nums.len();
    
    let mut first = -1;
    for i in 0..n {
        if prime_set.contains(&nums[i]) {
            first = i as i32;
            break;
        }
    }

    let mut last = -1;
    for i in (0..n).rev() {
        if prime_set.contains(&nums[i]) {
            last = i as i32;
            break;
        }
    }

    if first == -1 || last == -1 { 
        return 0; // 如果不存在质数
    }

    last - first
}

fn main() {
    let nums = vec![4, 2, 9, 5, 3];
    println!("{}", maximum_prime_difference(nums));
}