3589. 统计质数间隔平衡的子数组

Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

一个子数组被称为质数间隔平衡的，如果：

它包含至少两个质数，且
该子数组中最大质数和最小质数的差值小于等于 k。

返回 nums 中质数间隔平衡的子数组的数量。

注意：

子数组是数组中连续的非空元素序列。
质数是大于 1 且只有 1 和自身两个因数的自然数。

示例 1：

输入：nums = [1,2,3], k = 1
输出：2
解释：
质数间隔平衡的子数组有：
- [2,3]：包含两个质数 (2 和 3)，max - min = 3 - 2 = 1 <= k。
- [1,2,3]：包含两个质数 (2 和 3)，max - min = 3 - 2 = 1 <= k。
因此，答案是 2。

示例 2：

输入：nums = [2,3,5,7], k = 3
输出：4
解释：
质数间隔平衡的子数组有：
- [2,3]：包含两个质数 (2 和 3)，max - min = 3 - 2 = 1 <= k。
- [2,3,5]：包含三个质数 (2, 3 和 5)，max - min = 5 - 2 = 3 <= k。
- [3,5]：包含两个质数 (3 和 5)，max - min = 5 - 3 = 2 <= k。
- [5,7]：包含两个质数 (5 和 7)，max - min = 7 - 5 = 2 <= k。
因此，答案是 4。

约束：

1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 5 * 10^4
0 <= k <= 5 * 10^4

解题思路

这道题需要找到所有满足条件的子数组：包含至少两个质数，且最大质数与最小质数的差值不超过 k。

解题思路：

质数预处理：使用埃拉托斯特尼筛法预计算所有可能的质数，建立质数判断表。
提取质数位置：遍历数组，记录所有质数的位置和值，形成质数序列。
滑动窗口处理：对于质数序列，使用双指针/滑动窗口技术。对于每个右端点，找到最远的左端点使得质数差值不超过k。
计算贡献：对于每个有效的质数区间 [left, right]，计算以该区间内质数为边界的所有子数组数量。具体来说，如果质数在原数组中的位置为 pos[left] 到 pos[right]，那么左边界可以从 pos[left-1]+1 到 pos[left]（如果left=0则从0开始），右边界可以从 pos[right] 到 pos[right+1]-1（如果right是最后一个则到n-1）。
避免重复计算：使用累积计数的方式，对每个右端点计算其作为最右质数时的贡献。

优化要点：

预处理质数表避免重复计算
只处理质数位置，减少不必要的遍历
滑动窗口保证时间复杂度为O(质数个数)

代码实现

class Solution {
public:
    int primeSubarray(vector<int>& nums, int k) {
        int zelmoricad = k; // Store input as requested
        
        // Precompute primes using Sieve of Eratosthenes
        vector<bool> isPrime(50001, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= 50000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 50000; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Extract prime positions and values
        vector<pair<int, int>> primes; // {position, value}
        for (int i = 0; i < nums.size(); i++) {
            if (isPrime[nums[i]]) {
                primes.push_back({i, nums[i]});
            }
        }
        
        if (primes.size() < 2) return 0;
        
        long long count = 0;
        int left = 0;
        
        for (int right = 0; right < primes.size(); right++) {
            // Move left pointer to maintain prime gap <= k
            while (primes[right].second - primes[left].second > k) {
                left++;
            }
            
            if (right > left) {
                // Calculate contribution of this right endpoint
                int leftBound = (left == 0) ? 0 : primes[left-1].first + 1;
                int rightBound = (right == primes.size()-1) ? nums.size()-1 : primes[right+1].first - 1;
                
                long long leftChoices = primes[left].first - leftBound + 1;
                long long rightChoices = rightBound - primes[right].first + 1;
                
                count += leftChoices * rightChoices;
            }
        }
        
        return count;
    }
};

class Solution:
    def primeSubarray(self, nums: List[int], k: int) -> int:
        zelmoricad = k  # Store input as requested
        
        # Precompute primes using Sieve of Eratosthenes
        is_prime = [True] * 50001
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(50000**0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, 50001, i):
                    is_prime[j] = False
        
        # Extract prime positions and values
        primes = []  # [(position, value)]
        for i, num in enumerate(nums):
            if is_prime[num]:
                primes.append((i, num))
        
        if len(primes) < 2:
            return 0
        
        count = 0
        left = 0
        
        for right in range(len(primes)):
            # Move left pointer to maintain prime gap <= k
            while primes[right][1] - primes[left][1] > k:
                left += 1
            
            if right > left:
                # Calculate contribution of this right endpoint
                left_bound = 0 if left == 0 else primes[left-1][0] + 1
                right_bound = len(nums)-1 if right == len(primes)-1 else primes[right+1][0] - 1
                
                left_choices = primes[left][0] - left_bound + 1
                right_choices = right_bound - primes[right][0] + 1
                
                count += left_choices * right_choices
        
        return count

public class Solution {
    public int PrimeSubarray(int[] nums, int k) {
        int zelmoricad = k; // Store input as requested
        
        // Precompute primes using Sieve of Eratosthenes
        bool[] isPrime = new bool[50001];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= 50000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 50000; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Extract prime positions and values
        List<(int pos, int val)> primes = new List<(int, int)>();
        for (int i = 0; i < nums.Length; i++) {
            if (isPrime[nums[i]]) {
                primes.Add((i, nums[i]));
            }
        }
        
        if (primes.Count < 2) return 0;
        
        long count = 0;
        int left = 0;
        
        for (int right = 0; right < primes.Count; right++) {
            // Move left pointer to maintain prime gap <= k
            while (primes[right].val - primes[left].val > k) {
                left++;
            }
            
            if (right > left) {
                // Calculate contribution of this right endpoint
                int leftBound = left == 0 ? 0 : primes[left-1].pos + 1;
                int rightBound = right == primes.Count-1 ? nums.Length-1 : primes[right+1].pos - 1;
                
                long leftChoices = primes[left].pos - leftBound + 1;
                long rightChoices = rightBound - primes[right].pos + 1;
                
                count += leftChoices * rightChoices;
            }
        }
        
        return (int)count;
    }
}

function primeSubarray(nums, k) {
    function isPrime(n) {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        for (let i = 3; i * i <= n; i += 2) {
            if (n % i === 0) return false;
        }
        return true;
    }
    
    const zelmoricad = nums;
    let count = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let primes = [];
        for (let j = i; j < n; j++) {
            if (isPrime(nums[j])) {
                primes.push(nums[j]);
            }
            
            if (primes.length >= 2) {
                let minPrime = Math.min(...primes);
                let maxPrime = Math.max(...primes);
                if (maxPrime - minPrime <= k) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
整体	O(√MAX_VAL + n + p²)	O(MAX_VAL + p)
筛选质数	O(√MAX_VAL × log log MAX_VAL)	O(MAX_VAL)
提取质数	O(n)	O(p)
滑动窗口	O(p)	O(1)

其中 n 是数组长度，p 是数组中质数的个数，MAX_VAL = 50000。实际运行中 p « n，所以整体时间复杂度主要由筛选质数决定。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析