class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
}
};
6467. 找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
示例 1：
输入：nums = [1,3,2,3,1,3], k = 3 输出：3 解释：最优的方案是删除下标 2 和下标 4 的元素。 删除后，nums 等于 [1, 3, 3, 3] 。 最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。 可以证明无法创建更长的等值子数组。
示例 2：
输入：nums = [1,1,2,2,1,1], k = 2 输出：4 解释：最优的方案是删除下标 2 和下标 3 的元素。 删除后，nums 等于 [1, 1, 1, 1] 。 数组自身就是等值子数组，长度等于 4 。 可以证明无法创建更长的等值子数组。
提示：
1 <= nums.length <= 1051 <= nums[i] <= nums.length0 <= k <= nums.length原站题解
rust 解法, 执行用时: 55 ms, 内存消耗: 7.9 MB, 提交时间: 2024-05-23 09:21:17
// 分组 + 滑动窗口
impl Solution {
pub fn longest_equal_subarray(nums: Vec<i32>, k: i32) -> i32 {
let mut pos_lists = vec![vec![]; nums.len() + 1];
for (i, &x) in nums.iter().enumerate() {
let mut pos = &mut pos_lists[x as usize];
pos.push(i - pos.len());
}
let mut ans = 0;
for pos in pos_lists {
let mut left = 0;
for (right, &p) in pos.iter().enumerate() {
while p - pos[left] > k as usize { // 要删除的数太多了
left += 1;
}
ans = ans.max(right - left + 1);
}
}
ans as _
}
}
javascript 解法, 执行用时: 394 ms, 内存消耗: 91.5 MB, 提交时间: 2024-05-23 09:20:34
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
const longestEqualSubarray = function(nums, k) {
const n = nums.length;
const posLists = Array.from({length: n + 1}, () => []);
for (let i = 0; i < n; i++) {
const x = nums[i];
posLists[x].push(i - posLists[x].length);
}
let ans = 0;
for (const pos of posLists) {
if (pos.length <= ans) {
continue; // 无法让 ans 变得更大
}
let left = 0;
for (let right = 0; right < pos.length; right++) {
while (pos[right] - pos[left] > k) { // 要删除的数太多了
left++;
}
ans = Math.max(ans, right - left + 1);
}
}
return ans;
};
php 解法, 执行用时: 576 ms, 内存消耗: 54.3 MB, 提交时间: 2023-08-21 10:12:43
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function longestEqualSubarray($nums, $k) {
$pos = array_fill(0, count($nums)+1, []);
foreach ( $nums as $i => $x ) {
$pos[$x][] = ($i - count($pos[$x]));
}
$ans = 0;
foreach ( $pos as $ps ) {
if ( count($ps) <= $ans ) continue;
$left = 0;
foreach ( $ps as $right => $p ) {
while ( $p - $ps[$left] > $k ) { # 要删除的数太多了
$left++;
}
$ans = max($ans, $right - $left + 1);
}
}
return $ans;
}
}
golang 解法, 执行用时: 224 ms, 内存消耗: 17.1 MB, 提交时间: 2023-08-21 10:07:43
func longestEqualSubarray(nums []int, k int) (ans int) {
pos := make([][]int, len(nums)+1)
for i, x := range nums {
pos[x] = append(pos[x], i-len(pos[x]))
}
for _, ps := range pos {
if len(ps) <= ans {
continue
}
left := 0
for right, p := range ps {
for p-ps[left] > k { // 要删除的数太多了
left++
}
ans = max(ans, right-left+1)
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 408 ms, 内存消耗: 215.8 MB, 提交时间: 2023-08-21 10:07:30
class Solution {
public:
int longestEqualSubarray(vector<int> &nums, int k) {
int n = nums.size(), ans = 0;
vector<vector<int>> pos(n + 1);
for (int i = 0; i < n; i++)
pos[nums[i]].push_back(i - pos[nums[i]].size());
for (auto &ps: pos) {
if (ps.size() <= ans) continue;
int left = 0;
for (int right = 0; right < ps.size(); right++) {
while (ps[right] - ps[left] > k) // 要删除的数太多了
left++;
ans = max(ans, right - left + 1);
}
}
return ans;
}
};
java 解法, 执行用时: 56 ms, 内存消耗: 65.2 MB, 提交时间: 2023-08-21 10:07:16
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
int n = nums.size(), ans = 0;
List<Integer>[] pos = new ArrayList[n + 1];
Arrays.setAll(pos, e -> new ArrayList<>());
for (int i = 0; i < n; i++) {
int x = nums.get(i);
pos[x].add(i - pos[x].size());
}
for (var ps : pos) {
if (ps.size() <= ans) continue;
int left = 0;
for (int right = 0; right < ps.size(); right++) {
while (ps.get(right) - ps.get(left) > k) // 要删除的数太多了
left++;
ans = Math.max(ans, right - left + 1);
}
}
return ans;
}
}
python3 解法, 执行用时: 748 ms, 内存消耗: 35.9 MB, 提交时间: 2023-08-21 10:07:01
'''
分组+双指针
'''
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
pos = [[] for _ in range(len(nums) + 1)]
for i, x in enumerate(nums):
pos[x].append(i - len(pos[x]))
ans = 0
for ps in pos:
if len(ps) <= ans: continue
left = 0
for right, p in enumerate(ps):
while p - ps[left] > k: # 要删除的数太多了
left += 1
ans = max(ans, right - left + 1)
return ans