Leetcode每日一题 —— 2958. 最多 K 个重复元素的最长子数组

比较常规的哈希表 + 滑动窗口题。

class Solution {

public:

    int maxSubarrayLength(vector<int>& nums, int k) {

        // 找的是连续非空子序列，且涉及计数，应该是滑动窗口+哈希表

        unordered_map<int,int> cnts;

        int l=0,r=0;

        int n=nums.size();

        int res=0;

        while(r<n){

            // 当 nums[r] 计数已经等于 k 时，再加上当前这个 nums[r] 就超过了

            while(cnts[nums[r]]==k&&l<n){

                cnts[nums[l]]--;

                l++;

            }

            cnts[nums[r]]++;

            r++;

            res=max(res,r-l);

        }

        return res;

    }

};

算术评级 5 第 119 场双周赛 Q3 难度分 1535

也是不用怎么思考

class Solution:

    def maxSubarrayLength(self, nums: List[int], k: int) -> int:

        count=defaultdict(int)

        l=0

        count[nums[0]]+=1

        ans=1

        for i in range(1,len(nums)):

            count[nums[i]]+=1

            if count[nums[i]]>k:

                while nums[l]!=nums[i]:

                    count[nums[l]]-=1

                    l+=1

                count[nums[l]]-=1

                l+=1

            ans=max(ans,i-l+1)

        return ans

滑动滑动, btw,更新之后 ctrl + E 都不好使了,直接跳到谷歌搜索了

class Solution:

    def maxSubarrayLength(self, nums: List[int], k: int) -> int:

        from collections import defaultdict

        ans = 0

        n = len(nums)

        l = 0

        cnt = defaultdict(int)

        for r, x in enumerate(nums):

            cnt[x] += 1

            while cnt[x] > k:

                cnt[nums[l]] -= 1

                l += 1

            ans = max(ans, r - l + 1)

        return ans

Note: defaultdict比Counter快好多

class Solution:

    def maxSubarrayLength(self, nums: List[int], k: int) -> int:

        n = len(nums)

        cnt = defaultdict(int)



        ans = left = 0

        for right in range(n):

            cnt[nums[right]] += 1

            while cnt[nums[right]] > k:

                cnt[nums[left]] -= 1

                left += 1

            ans = max(ans, right - left + 1)

        return ans