MediumRating 1467

3719. Longest Balanced Subarray I

arrayhash-tabledivide-and-conquersegment-treeprefix-sum

解題說明

Longest Balanced Subarray I

題目描述：給定一個整數陣列 nums，定義一個子陣列為「平衡」的，若其中每個不同元素的出現次數都相同。求最長平衡子陣列的長度。

解題思路：利用前綴和與雜湊表的技巧。設想一個子陣列 nums[i..j] 是平衡的，意味著每個不同元素出現的次數相同。可以用「頻率差值」的向量來表示狀態：選定一個基準元素，計算每個元素相對於它的出現次數差值。若兩個前綴位置 i 和 j 有相同的差值向量，則 nums[i+1..j] 是平衡的。

具體做法：維護每個元素的累計出現次數，將最小頻率歸零（即所有頻率減去最小值），這個歸零後的狀態若之前出現過，則找到一個平衡子陣列。用雜湊表記錄每個狀態第一次出現的位置。

C++ 解法

複雜度分析

時間複雜度：O(n * d) — 遍歷陣列一次，每個位置計算 d-1 維的狀態向量。d 為不同元素的個數。

空間複雜度：O(n * d) — 雜湊表最多存 n 個不同的狀態，每個狀態 d-1 維。

虛擬碼

1. Find all distinct values, map them to indices 0..d-1
2. Initialize frequency array freq[0..d-1] = 0
3. Define state = (freq[1]-freq[0], freq[2]-freq[0], ..., freq[d-1]-freq[0])
4. Store firstSeen[initial_state] = 0
5. For each index i:
   a. Increment freq[valIdx[nums[i]]]
   b. Compute state vector
   c. If state seen before: update maxLen = max(maxLen, i+1 - firstSeen[state])
   d. Else: store firstSeen[state] = i+1
6. Return maxLen

其他解法

枚舉目標頻率 O(n * max_freq)：對每個可能的目標頻率 c，用滑動窗口找最長的子陣列使得所有出現的元素恰好出現 c 次。需要仔細維護窗口內的頻率計數。

暴力法 O(n²)：枚舉所有子陣列，統計每個子陣列內各元素的出現次數，檢查是否平衡。簡單但慢。

延伸思考

如果「平衡」定義為每個元素出現次數之差不超過 1（而非完全相同），如何修改？
若需要找到所有最長平衡子陣列的起始位置，如何一併回傳？
在串流場景下（元素逐個到達），能否在線計算當前最長平衡子陣列？

Longest Balanced Subarray I — CaffeCode