MediumRating 2235

3589. Count Prime-Gap Balanced Subarrays

arraymathqueuesliding-windownumber-theorymonotonic-queue

解題說明

Count Prime-Gap Balanced Subarrays

題目描述：給定一個整數陣列 nums，若一個子陣列的最大值與最小值之差為質數，則稱該子陣列為「質數間隔平衡」子陣列。回傳陣列中質數間隔平衡子陣列的數量。

解題思路：需要枚舉所有子陣列並檢查其 max - min 是否為質數。暴力枚舉所有 O(n²) 個子陣列，同時用單調佇列高效維護滑動窗口的最大值和最小值。對於質數判斷，由於數值範圍有限，可以預先用篩法產生質數表。固定左端點 l，右端點 r 從 l 向右擴展，每次用單調佇列 O(1) 取得當前窗口的 max 和 min，檢查差值是否為質數。

C++ 解法

複雜度分析

時間複雜度：O(n² + D) — 枚舉所有子陣列 O(n²)，篩法 O(D)，D 為最大差值。

空間複雜度：O(D) — 質數篩的空間。

虛擬碼

1. Compute max possible difference D = max(nums) - min(nums)
2. Build prime sieve up to D
3. For each left endpoint l from 0 to n-1:
   a. Track running max and min
   b. For each right endpoint r from l to n-1:
      - Update max and min with nums[r]
      - If max - min is prime, increment count
4. Return count

其他解法

單調佇列 + 雙指標 O(n * sqrt(D))：固定左端點，用兩個單調佇列追蹤窗口 max/min。但由於沒有單調性（差值不隨窗口擴大而單調），無法直接用滑動窗口剪枝，仍需枚舉所有子陣列。

分治法 O(n log n)：將陣列分為左右兩半，分別計算內部的答案，再合併跨越中點的子陣列。合併時需要高效枚舉 max/min 的組合，實作較複雜。

延伸思考

如果改為「差值為完全平方數」，如何調整檢查邏輯？
若需要回傳所有質數間隔平衡子陣列的起始和結束索引，而非僅計數，如何實現？
陣列中有負數時，差值的定義是否改變？如何處理？

Count Prime-Gap Balanced Subarrays — CaffeCode