🔗 🟡 2831. Find the Longest Equal Subarray 1976

tags: `Weekly Contest 359` `滑動窗口(Sliding Window)` `雜湊表(Hash Table)`

題意

給定一個下標從 $0$ 開始的整數陣列 $nums$ 和一個整數 $k$ 。

相等子陣列(Equal Subarray) 是指子陣列中所有元素都相等。值得留意的是，空子陣列也是 相等子陣列。

從 $nums$ 中刪除最多 $k$ 個元素後，返回可能的最長 相等子陣列 的長度。

限制

$1 \leq nums.length \leq 10^5$
$1 \leq nums[i] \leq nums.length$
$0 \leq k \leq nums.length$

思路：滑動窗口(Sliding Window) + 雜湊表(Hash Table)

由於要使子陣列中的所有元素皆相同，我們可以固定一個元素 $x$ ，枚舉以 $x$ 作為開頭和結尾的子陣列，根據題意，子陣列中最多只有 $k$ 個元素與 $x$ 不同，因此可以維護一個窗口，使得窗口內的元素與 $x$ 的個數差不超過 $k$ 。

首先紀錄每個元素出現的位置，令 $pos[x]$ 為元素 $x$ 出現的位置列表，列表中的元素為 $x$ 在原陣列中的下標。

可以直接用雜湊表來實現， Python 中使用 defaultdict(list)，C++ 中使用 vector<vector<int>> 即可。
但注意到限制中 $1 \leq nums[i] \leq n$ ，因此也可以用長度為 $n+1$ 的二維陣列來實現，其中 $n$ 為 $nums$ 的長度。

接著枚舉每個元素 $x$ ，以該元素為窗口的左右邊界，令 $left, right$ 為窗口的左右邊界，指向 $pos[x]$ 中的下標，枚舉右端點 $right$ 。

則 $pos[x][right] - pos[x][left] + 1$ 為目前窗口在原陣列中的長度，也就是子陣列的長度。
$right - left + 1$ 為目前窗口內元素 $x$ 的數量。
兩者相減，即為窗口內非 $x$ 元素的數量，也就是需要刪除的元素數量，若大於 $k$ ，則需要開始縮小窗口，最後更新答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為陣列 $nums$ 的長度，需要遍歷所有元素。
空間複雜度： $\mathcal{O}(n)$ ，需要 $\mathcal{O}(n)$ 的空間來存儲每個元素出現的位置。

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pos = defaultdict(list) # 紀錄每個元素出現的位置
        for i, x in enumerate(nums):
            pos[x].append(i)
        ans = 0
        for x, lst in pos.items(): 
            left = 0 # left, right 為窗口的左右邊界，是 pos[x] 中的下標
            for right, idx in enumerate(lst):
                while (idx - lst[left] + 1) - (right - left + 1) > k: # 若不符合條件，則開始縮小窗口
                    left += 1
                ans = max(ans, right - left + 1) # 更新答案
        return ans

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> pos(n + 1); // 紀錄每個元素出現的位置，1 <= nums[i] <= nums.length
        for (int i = 0; i < n; i++) { 
            pos[nums[i]].push_back(i);
        }
        int ans = 0;
        for (int x = 1; x <= n; x++){
            if (pos[x].empty()) continue; // 若元素 x 不存在，則跳過
            int left = 0; // left, right 為窗口的左右邊界，是 pos[x] 中的下標
            for (int right = 0; right < pos[x].size(); right++) {
                while ((pos[x][right] - pos[x][left] + 1) - (right - left + 1) > k) { // 若不符合條件，則開始縮小窗口
                    left++;
                }
                ans = max(ans, right - left + 1); // 更新答案
            }
        }
        return ans;
    }
};