2025-12-03：计数质数间隔平衡子数组。用go语言，给定一个整数数组 nums 和一个整数 k。请计算数组中有多少个连续且非空的子序列满足下面两个条件：
1. 子序列中至少包含两个质数；
2. 该子序列里所有质数中的最大值与最小值之差不超过 k。
这里“子序列”指的是数组中位置相邻的一段元素（即常说的子数组）。质数指大于 1 且只有 1 和自身两个约数的正整数。返回符合上述条件的子序列数量。
1
1
0
输入：nums = [2,3,5,7], k = 3。
输出：4。
解释：
质数间隔平衡子数组有：
[2,3]：包含 2 个质数（2 和 3），最大值 - 最小值 = 3 - 2 = 1
[2,3,5]：包含 3 个质数（2，3 和 5），最大值 - 最小值 = 5 - 2 = 3
[3,5]：包含 2 个质数（3 和 5），最大值 - 最小值 = 5 - 3 = 2
[5,7]：包含 2 个质数（5 和 7），最大值 - 最小值 = 7 - 5 = 2
因此，答案为 4。
题目来自力扣3589。
算法过程详解
该Go语言程序用于统计满足特定条件的连续子数组（子序列）数量。以下是大体过程的详细分步描述：
1. 质数预计算（初始化阶段）
• 程序使用埃拉托斯特尼筛法预计算所有小于50,001的质数。全局数组np用于标记非质数（np[i]为true表示i不是质数）。
• 筛法从2开始遍历到√mx，对每个质数i，标记其所有倍数（从i*i开始）为非质数。这一步确保在后续处理中能以O(1)时间判断任意数是否为质数。
2. 滑动窗口遍历主逻辑
函数primeSubarray使用双指针（滑动窗口） 结合单调队列来动态维护窗口内的质数极值：
• 初始化：
• left：窗口左边界，初始为0。
• last和last2：分别记录当前窗口内最近一个和倒数第二个质数的位置，初始为-1。
• minQ和maxQ：单调队列（双端队列），分别维护当前窗口内质数索引的递增（最小值队列）和递减（最大值队列）顺序。
• 遍历数组（右指针扩张）：
• 对每个元素nums[i]，若它是质数（!np[x]为真）：
1. 更新质数位置：
last2记录上一个质数位置（last），last更新为当前索引i。这确保窗口内至少有两个质数时，last2有效。
2. 维护单调队列：
最小值队列minQ：从队尾移除所有对应质数大于等于当前质数的索引，保持队列严格递增。
最大值队列maxQ：从队尾移除所有对应质数小于等于当前质数的索引，保持队列严格递减。
然后将当前索引i加入两队。
3. 调整窗口左边界（收缩）：
若当前窗口内最大质数与最小质数之差（即nums[maxQ[0]] - nums[minQ[0]]）超过k，则右移左边界left。同时，清理minQ和maxQ中队首小于left的索引（这些索引已离开窗口）。
• 统计有效子数组：
每处理一个元素后（无论是否为质数），若窗口内至少有两个质数（last2 ≠ -1），则计算以i结尾的有效子数组数量：
左边界范围是[left, last2]，因为子数组必须包含last2和last两个质数。因此，答案增加last2 - left + 1。
3. 结果返回
• 遍历结束后，返回累加值ans，即所有满足条件的子数组数量。
复杂度分析
• 时间复杂度：
质数筛预计算：O(mx log log mx) ≈ O(50,000 log log 50,000)，可视为常数级。
主遍历：数组长度为n，每个元素最多被加入/移除单调队列一次，均摊操作O(1)。因此总时间复杂度为 O(n)。
• 空间复杂度：
固定数组np占用O(mx) ≈ O(50,000)，为常数空间。
单调队列minQ和maxQ最坏情况下存储O(n)个索引。因此总额外空间复杂度为 O(n)。
关键点总结
• 通过质数筛实现O(1)质数判断，避免每次重复计算。
• 单调队列高效维护滑动窗口内的极值，确保质数差约束的实时检查。
• 利用last2记录倒数第二个质数位置，直接确定有效左边界范围，避免暴力枚举。
Go完整代码如下：
package main
import (
"fmt"
)
const mx = 50_001
var np = [mx]bool{1: true} // 1 不是质数
func init {
for i := 2; i*i
if !np[i] {
for j := i * i; j
np[j] = true
}
}
}
}
func primeSubarray(nums []int, k int) (ans int) {
var minQ, maxQ []int
last, last2 := -1, -1
left := 0
for i, x := range nums {
if !np[x] {
// 1. 入
last2 = last
last = i
forlen(minQ) > 0 && x
minQ = minQ[:len(minQ)-1]
}
minQ = append(minQ, i)
forlen(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
maxQ = maxQ[:len(maxQ)-1]
}
maxQ = append(maxQ, i)
// 2. 出
for nums[maxQ[0]]-nums[minQ[0]] > k {
left++
if minQ[0]
minQ = minQ[1:]
}
if maxQ[0]
maxQ = maxQ[1:]
}
}
}
// 3. 更新答案
ans += last2 - left + 1
}
return
}
func main {
nums := []int{2, 3, 5, 7}
k := 3
result := primeSubarray(nums, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
from collections import deque
# 预处理质数
MX = 50001
np = [False] * MX
np[0] = np[1] = True # 0 和 1 不是质数
for i in range(2, int(MX ** 0.5) + 1):
if not np[i]:
for j in range(i * i, MX, i):
np[j] = True
def primeSubarray(nums: List[int], k: int) -> int:
ans = 0
min_q = deque # 单调递增队列（最小值的索引）
max_q = deque # 单调递减队列（最大值的索引）
last = -1 # 最近一个质数的索引
last2 = -1 # 倒数第二个质数的索引
left = 0 # 窗口左边界
for i, x in enumerate(nums):
if not np[x]: # x 是质数
# 1. 更新质数索引
last2 = last
last = i
# 维护最小值的单调递增队列
while min_q and x
min_q.pop
min_q.append(i)
# 维护最大值的单调递减队列
while max_q and x >= nums[max_q[-1]]:
max_q.pop
max_q.append(i)
# 2. 调整窗口左边界，确保窗口内最大最小差值
while nums[max_q[0]] - nums[min_q[0]] > k:
left += 1
if min_q[0]
min_q.popleft
if max_q[0]
max_q.popleft
# 3. 更新答案（累加以当前元素结尾的有效子数组数量）
ans += max(0, last2 - left + 1)
return ans
if __name__ == "__main__":
nums = [2, 3, 5, 7]
k = 3
result = primeSubarray(nums, k)
print(result) # 输出结果
C++完整代码如下：
#include
#include
#include
#include
using namespace std;
constint MX = 50001;
bool np[MX] = {false};
// 初始化质数筛
void init {
np[0] = np[1] = true; // 0和1不是质数
for (int i = 2; i * i
if (!np[i]) {
for (int j = i * i; j
np[j] = true;
}
}
}
}
int primeSubarray(vector& nums, int k) {
int ans = 0;
deque minQ; // 单调递增队列（最小值的索引）
deque maxQ; // 单调递减队列（最大值的索引）
int last = -1; // 最近一个质数的索引
int last2 = -1; // 倒数第二个质数的索引
int left = 0; // 窗口左边界
for (int i = 0; i
int x = nums[i];
if (!np[x]) { // x是质数
// 1. 更新质数索引
last2 = last;
last = i;
// 维护最小值的单调递增队列
while (!minQ.empty && x
minQ.pop_back;
}
minQ.push_back(i);
// 维护最大值的单调递减队列
while (!maxQ.empty && x >= nums[maxQ.back]) {
maxQ.pop_back;
}
maxQ.push_back(i);
// 2. 调整窗口左边界，确保窗口内最大最小差值
while (nums[maxQ.front] - nums[minQ.front] > k) {
left++;
if (!minQ.empty && minQ.front
minQ.pop_front;
}
if (!maxQ.empty && maxQ.front
maxQ.pop_front;
}
}
}
// 3. 更新答案（累加以当前元素结尾的有效子数组数量）
if (last2 >= left) {
ans += last2 - left + 1;
}
}
return ans;
}
int main {
// 初始化质数筛
init;
vector nums = {2, 3, 5, 7};
int k = 3;
int result = primeSubarray(nums, k);
cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。