Day59 | 灵神 | 滑动窗口：最多K个重复元素的最长子数组&&找到最长的半重复子字符串

##2958.最多K个重复元素的最长子数组

2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode）

思路：

和3. 无重复字符的最长子串 - 力扣（LeetCode）可以说是一模一样，可以查看我昨天的题解

无重复最长子串是这道题K等于2的情况而已

即左指针移动的条件是把右端点包含在好数组内时，右端点nums[i]代表的数字个数超过了k。那我们就移动左指针，直到固定右端点时整个子数组都满足数字个数小于等于k的条件。

完整代码：

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

2730.找到最长的半重复子字符串

2730. 找到最长的半重复子字符串 - 力扣（LeetCode）

思路：

还是和前面的思路相同，固定遍历右端点，然后根据具体条件收缩左指针。

本题左指针往后移动的条件是 在左右指针之间有一对以上的相邻字符相等。

那我们就自然而然想到拿一个变量来记录相邻字符相等的数量，如果大于1，说明满足了条件，我们应该向后移动左指针，直到左指针满足条件了为止，而怎么判断左指针满足条件该停止移动了又是新的难点。

我们先往右移动1个字符，这样就可以比较l和l-1所指的字符，如果不相等，那说明我们没有找到第一对相等的相邻字符，我们就继续往后移动，只有l和l-1相等的时候，我们才达到了左指针停止移动的条件，就是左右指针之间已经没有1对以上的相邻相等字符了。（当前第一对相等的相邻字符是l和l-1，而我们的窗口是l到r，[l,r]，不包括l-1，自然也就排除了第一对相等的相邻字符）

完整代码：

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
class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int res=0;
        int l=0;
        int flag=0;
        for(int i=0;i<s.size();i++)
        {
            //记录相邻字符相等的对数
            if(i>0&&s[i]==s[i-1])
                flag++;
            //对数大于1
            if(flag>1)
            {
               l++;
               //左指针移动停止的条件 就是找到第一对相等的相邻字符
               while(s[l]!=s[l-1]) 
                    l++;
                //更新flag
                flag=1;
            }
            res=max(res,i-l+1);
        }
        return res;
    }
};