Loading... > https://leetcode.cn/problems/find-the-longest-equal-subarray/description/?envType=daily-question&envId=2024-05-06 ### 滑动窗口 最长等值子数组里都是同一个元素，所以要找出删除至多 $k$ 个元素后最长等值子数组的长度，只需要找出每种元素在满足间隔小于等于 $k$ 的情况下最多能有几个。 因此可以统计所有元素的位置，然后用一个滑动窗口来找到各个元素所有的可行区间，找到数量最大值即可。 ```c++ class Solution { public: int longestEqualSubarray(std::vector<int>& nums, int k) { const int n = nums.size(); if (n == 0) return 0; std::unordered_map<int, std::vector<int>> positions; for (int i = 0; i < n; i++) positions[nums[i]].push_back(i); int left, right, end, res = 0; for (auto &[num, pos] : positions) { left = 0, right = 0, end = pos.size() - 1; while (right < end) { if (right - left > res) res = right - left; while (pos[right + 1] - pos[left] - (right - left + 1) > k) ++left; ++right; } if (right - left > res) res = right - left; } return res + 1; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为 `nums` 数组的长度。分组需要 $O(n)$ 的时间复杂度，通过滑动窗口找到每种元素的最大长度需要遍历所有连续相等字符的长度计数，最多有 $n$ 个。因此总的时间复杂度为 $O(n)$ 。 - 空间复杂度：$O(n)$ 。 ### 优化 等值子数组一定有相同的左右端点元素且左端点的值为区间内的众数，因此我们只需要计算满足左右端点相同且该元素为众数的区间即可。题目要求删除至多 $k$ 个元素，那么只需要保证区间内非目标元素小于等于 $k$ 即可。 这里我们选择枚举右边界 $r$ ，此时对于左边界 $l$ ： - 如果 $nums[l] = nums[r]$ 且其余元素的个数大于 $k$ 时，区间向右移动； - 如果 $nums[l] \neq nums[r]$ 且其余元素的个数大于 $k$ 时，此时 `num[l]` 一定不是目标等值元素，跳过并将区间向右移动； - 统计所有区间并寻找最优解。 ```c++ class Solution { public: int longestEqualSubarray(std::vector<int>& nums, int k) { const int n = nums.size(); int res = 0; std::vector<int> cnt(n + 1); for (int left = 0, right = 0; right < n; right++) { ++cnt[nums[right]]; while (right - left + 1 - cnt[nums[left]] > k) --cnt[nums[left++]]; res = std::max(res, cnt[nums[right]]); } return res; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为 `nums` 数组的长度。 - 空间复杂度：$O(n)$ 。 最后修改：2024 年 05 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏