徐州网站建设 网站推广怎么网站推广

题目：

给你一个整数数组 nums。
返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。

示例 1：
输入： nums = [4,2,9,5,3]
输出： 3
解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：
输入： nums = [4,8,2,8]
输出： 0
解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：
1 <= nums.length <= 3 * 10⁵
1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。

思路：

打表，将100以内的质数先穷举出来,然后用一个tmp记录第一个质数的下标，后面每遇到一个质数就去更新ans

代码：

class Solution {// 打表，将100以内的质数先穷举出来// 然后用一个tmp记录第一个质数的下标，后面每遇到一个质数就去更新anspublic int maximumPrimeDifference(int[] nums) {Set<Integer> primes = new HashSet<>(Arrays.asList(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));int n = nums.length;int tmp = -1, ans = 0;for (int i = 0; i < n; ++i) {if (primes.contains(nums[i])) {if (tmp != -1) {ans = Math.max(ans, i - tmp);} else {tmp = i;}}}return ans;}
}