Loading... > https://leetcode.cn/problems/maximum-prime-difference/description/?envType=daily-question&envId=2024-05-02 简单题，`nums[i]` 的范围在 $[1, 100]$ 之间，因此直接构造一个质数表，然后使用双指针从左右同时搜索，即为下标的最大距离。 ```c++ class Solution { public: int maximumPrimeDifference(std::vector<int>& nums) { bool graph[107]; memset(graph, 0, sizeof(graph)); graph[0] = graph[1] = true; for (int i = 2; i < 107; i++) { if (graph[i]) continue; for (int j = 2; i * j < 107; j++) graph[i * j] = true; } int begin = 0, end = nums.size() - 1; while (graph[nums[begin]]) begin++; while (graph[nums[end]]) end--; return end - begin; } }; ``` - 时间复杂度：$O(n + CloglogC)$ ，其中 $n$ 为 `nums` 数组的大小，$C$ 为元素的取值范围，本题中固定为 100 。 - 空间复杂度：$O(C)$ 。这里通过数组存储，所以是 $O(C)$ 。 最后修改：2024 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏