跳转至

3641. 最长半重复子数组 🔒

题目描述

给定一个长度为  n 的整数数组 nums 和一个整数 k。

半重复 子数组是指最多有 k 个元素重复（即出现超过一次）的连续子数组。

返回 nums 中最长 半重复 子数组的长度。

 

示例 1：

输入：nums = [1,2,3,1,2,3,4], k = 2

输出：6

解释：

最长的半重复子数组是 [2, 3, 1, 2, 3, 4]，其中有 2 个重复元素（2 和 3）。

示例 2：

输入：nums = [1,1,1,1,1], k = 4

输出：5

解释：

最长的半重复子数组是 [1, 1, 1, 1, 1]，其中只有 1 个重复元素（1）。

示例 3：

输入：nums = [1,1,1,1,1], k = 0

输出：1

解释：

最长的半重复子数组是 [1]，其中没有重复元素。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 0 <= k <= nums.length

解法

方法一：滑动窗口

我们使用双指针 \(l\) 和 \(r\) 维护一个滑动窗口，右指针不断向右移动，并使用哈希表 \(\textit{cnt}\) 记录每个元素在当前窗口内出现的次数。

当某个元素的出现次数从 \(1\) 变为 \(2\) 时，表示当前有一个新的重复元素，我们将重复元素的计数器 \(\textit{cur}\) 加 \(1\)。当重复元素的计数器大于 \(k\) 时，说明当前窗口不满足条件，我们需要移动左指针，直到重复元素的计数器不大于 \(k\) 为止。在移动左指针的过程中，如果某个元素的出现次数从 \(2\) 变为 \(1\)，表示当前少了一个重复元素，我们将重复元素的计数器减 \(1\)。然后，我们更新答案，即 \(\textit{ans} = \max(\textit{ans}, r - l + 1)\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestSubarray(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = cur = l = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            cur += cnt[x] == 2
            while cur > k:
                cnt[nums[l]] -= 1
                cur -= cnt[nums[l]] == 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0, cur = 0, l = 0;
        for (int r = 0; r < nums.length; ++r) {
            if (cnt.merge(nums[r], 1, Integer::sum) == 2) {
                ++cur;
            }
            while (cur > k) {
                if (cnt.merge(nums[l++], -1, Integer::sum) == 1) {
                    --cur;
                }
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int ans = 0, cur = 0, l = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (++cnt[nums[r]] == 2) {
                ++cur;
            }
            while (cur > k) {
                if (--cnt[nums[l++]] == 1) {
                    --cur;
                }
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func longestSubarray(nums []int, k int) (ans int) {
    cnt := make(map[int]int)
    cur, l := 0, 0
    for r := 0; r < len(nums); r++ {
        if cnt[nums[r]]++; cnt[nums[r]] == 2 {
            cur++
        }
        for cur > k {
            if cnt[nums[l]]--; cnt[nums[l]] == 1 {
                cur--
            }
            l++
        }
        ans = max(ans, r-l+1)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function longestSubarray(nums: number[], k: number): number {
    const cnt: Map<number, number> = new Map();
    let [ans, cur, l] = [0, 0, 0];
    for (let r = 0; r < nums.length; r++) {
        cnt.set(nums[r], (cnt.get(nums[r]) || 0) + 1);
        if (cnt.get(nums[r]) === 2) {
            cur++;
        }

        while (cur > k) {
            cnt.set(nums[l], cnt.get(nums[l])! - 1);
            if (cnt.get(nums[l]) === 1) {
                cur--;
            }
            l++;
        }

        ans = Math.max(ans, r - l + 1);
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::collections::HashMap;

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
        let mut cnt = HashMap::new();
        let mut ans = 0;
        let mut cur = 0;
        let mut l = 0;

        for r in 0..nums.len() {
            let entry = cnt.entry(nums[r]).or_insert(0);
            *entry += 1;
            if *entry == 2 {
                cur += 1;
            }

            while cur > k {
                let entry = cnt.entry(nums[l]).or_insert(0);
                *entry -= 1;
                if *entry == 1 {
                    cur -= 1;
                }
                l += 1;
            }

            ans = ans.max(r - l + 1);
        }

        ans as i32
    }
}

评论